Prawdopodobieństwo - liczby względnie pierwsze

[Wasilewski]

Gdzieś tu na forum wyczytałem, że jeśli rozważymy zbiór:\(\displaystyle{ \lbrace 1,2, \ldots n-1, n\rbrace}\) i wylosujemy z niego 2 liczby, a prawdopodobieństwo tego, że są względnie pierwsze oznaczymy jako \(\displaystyle{ P_{n}}\), to zachodzi:
\(\displaystyle{ \lim_{n\to \infty} P_{n} = \frac{6}{\pi^2}}\)
Jako że mnie to zaciekawiło, to próbowałem jakoś dojść do tego, ale mi się nie udało. Kombinowałem tak: dla każdej liczby k pasują nam wszystkie liczby względnie pierwsze z nią, mniejsze od niej (bo rozważamy wszystkie k od 1 do n). Zatem powinno to wyglądać tak:
\(\displaystyle{ P_{n} = \frac{\sum_{k=1}^{n} \varphi(k)}{{n\choose 2}}}\)
No i tu nie mam pojęcia, co począć. Chciałbym się najpierw upewnić, że na razie jest dobrze. Z góry dziękuję za odpowiedzi.

[max]

Jest ok, ale też nie bardzo wiem jak to dalej ruszyć:)

Ja zrobiłem to korzystając z tego, że dwie liczby są względnie pierwsze gdy nie istnieje liczba pierwsza, która by dzieliła obie te liczby, i ze znanej równości: \(\displaystyle{ \prod_{p}\frac{1}{1 - \frac{1}{p^{2}}} = \zeta(2)}\), gdzie \(\displaystyle{ p}\) 'przebiega' zbiór liczb pierwszych.
Poniżej są szczegóły.

Niech \(\displaystyle{ \mathcal{P}_{n}}\) oznacza zbiór liczb pierwszych mniejszych od \(\displaystyle{ n}\).
Dla \(\displaystyle{ p\in \mathcal{P}_{n}}\) przy ustalonym \(\displaystyle{ n}\) przyjmujemy za \(\displaystyle{ A_{p}^{n}}\) zdarzenie takie, że \(\displaystyle{ p}\) nie dzieli obu wybranych liczb.
Liczymy prawdopodobieństwo zdarzenia przeciwnego, czyli takiego, że \(\displaystyle{ p}\) dzieli obie wylosowane liczby.
Dla ustalonej liczby \(\displaystyle{ kp}\) - większej z liczb podzielnych przez \(\displaystyle{ p}\) mniejszą możemy wylosować na \(\displaystyle{ k - 1}\) sposobów, przy czym oczywiście \(\displaystyle{ k = 1, 2, \ldots, \left\lfloor\frac{n}{p}\right\rfloor}\).
Zatem prawdopodobieństwo zdarzenia przeciwnego do \(\displaystyle{ A_{p}^{n}}\) wynosi:

\(\displaystyle{ 1 - P(A_{p}^{n}) = \frac{\sum_{k = 1}^{\left\lfloor\frac{n}{p}\right\rfloor}k - 1}{{n\choose 2}} = \frac{\left\lfloor\frac{n}{p}\right\rfloor\left(\left\lfloor\frac{n}{p}\right\rfloor - 1\right)}{n(n - 1)}}\)

Stąd:

\(\displaystyle{ P(A_{p}^{n}) = 1 - \frac{\left\lfloor\frac{n}{p}\right\rfloor\left(\left\lfloor\frac{n}{p}\right\rfloor - 1\right)}{n(n - 1)}}\)

Przydadzą się jeszcze dwa szacowania, wynikające bezpośrednio z definicji części całkowitej i powyższej równości:

\(\displaystyle{ \frac{P(A_{p}^{n})}{1 - \frac{1}{p^{2}}} \geqslant \frac{1 - \frac{n - p}{p^{2}(n - 1)}}{1 - \frac{1}{p^{2}}} = \frac{p^{2}- 1 + \frac{p - 1}{n - 1}}{p^{2} - 1}=1 + \frac{1}{(n - 1)(p+1)}> 1}\)

\(\displaystyle{ \frac{P(A_{p}^{n})}{1 - \frac{1}{p^{2}}} \leqslant \frac{1 - \frac{(n - p)(n - 2p)}{p^{2}n(n - 1)}}{1 - \frac{1}{p^{2}}} = \frac{p^{2} - 1 - \frac{(n - p)(n - 2p) - n(n - 1)}{n(n - 1)}}{p^{2} - 1} =\\
= 1 + \frac{(3p - 1)n - 2p^{2}}{(p^{2} - 1)n(n - 1)}\leqslant 1 +\frac{3}{(n - 1)(p - 1)}}\)

Wracając do naszych rozważań, zauważamy, że:

\(\displaystyle{ P_{n} = \prod_{p\in \mathcal{P}_{n}}P(A_{p}^{n})}\)

i robimy użytek z powyższych szacowań oraz z nierówności między średnimi:

\(\displaystyle{ \frac{P_{n}}{\prod_{p\in \mathcal{P}_{n}}\left(1 - \frac{1}{p^{2}}\right)} \leqslant \prod_{p\in\mathcal{P}_{n}}\left(1 + \frac{3}{(n - 1)(p - 1)}\right)\leqslant\\
\leqslant \left(1 + \frac{\sum_{p\in\mathcal{P}_{n}}\frac{3}{(n - 1)(p - 1)}}{\pi(n)}\right)^{\pi(n)} = \left(1 + \frac{3\sum_{p\in\mathcal{P}_{n}}\frac{1}{p - 1}}{(n-1)\pi(n)}\right)^{\pi(n)} \leqslant\\
\leqslant \left(1 + \frac{3\sum_{k = 1}^{\pi(n)}\frac{1}{k}}{(n-1)\pi(n)}\right)^{\pi(n)}\leqslant \left(1 + \frac{3(1 + \ln\pi(n))}{(n-1)\pi(n)}\right)^{\pi(n)} \to 1}\)

gdyż \(\displaystyle{ \pi(n) < n}\) gdzie \(\displaystyle{ \pi(n)}\) oznacza liczbę elementów zbioru \(\displaystyle{ \mathcal{P}_{n}}\), a ostatnia z nierówności to nierówność \(\displaystyle{ \sum_{k=1}^{m}\frac{1}{k} < 1 + \ln m}\), którą można uzyskać np szacując całkę \(\displaystyle{ \int_{1}^{m}\frac{1}{x}\, dx}\) metodą prostokątów.
Z drugiej strony:

\(\displaystyle{ \frac{P_{n}}{\prod_{p\in \mathcal{P}_{n}}\left(1 - \frac{1}{p^{2}}\right)}\geqslant 1}\)

Zatem:

\(\displaystyle{ \lim_{n\to \infty}\frac{P_{n}}{\prod_{p\in \mathcal{P}_{n}}\left(1 - \frac{1}{p^{2}}\right)} = 1}\)

A ponieważ:

\(\displaystyle{ \lim_{n\to \infty}\prod_{p\in \mathcal{P}_{n}}\left(1 - \frac{1}{p^{2}}\right) = \lim_{n\to \infty}\left(\prod_{p\in \mathcal{P}_{n}}\frac{1}{1 - \frac{1}{p^{2}}}\right)^{-1} = \\
= \lim_{n\to \infty}\left(\prod_{p\in\mathcal{P}_{n}}\left(\sum_{k = 0}^{\infty}\frac{1}{p^{2k}}\right)\right)^{-1} = \left(\sum_{k = 1}^{\infty}\frac{1}{k^{2}}\right)^{-1} = \frac{6}{\pi^{2}}}\)

to \(\displaystyle{ \lim_{n\to\infty}P_{n} = \frac{6}{\pi^{2}}}\).

[Wasilewski]

Świetnie, dzięki; coś mi się wydaje, że sam bym na to nie wpadł.