György Pólya i jego losowe przechadzki (1921)

György (a potem George) Pólya należał do wyjątkowej konstelacji wybitnych matematyków i fizyków pochodzących z Węgier początku XX wieku. Matematyka nie była jego wczesną pasją, zajął się nią poważniej dopiero po kilku latach studiów, wcześniej interesował się literaturą, zdobył uprawnienia do nauczania łaciny i wegierskiego w gimnazjum, zajmował się filozofią. Podsumował to kiedyś żartobliwie: „Uważałem, że nie jestem dość dobry na fizykę, a zbyt dobry na filozofię. Matematyka leży gdzieś pomiędzy”. Podróżował w poszukiwaniu wiedzy, jak tylu studentów przed pierwszą wojną światową, zwłaszcza Żydów. Uczył się matematyki w Budapeszcie, Wiedniu, Getyndze i Paryżu, w 1914 r., dwa lata po doktoracie, otrzymał posadę Privatdozenta w ETH w Zurychu. Minął się w ten sposób z Albertem Einsteinem, który właśnie w roku 1914 wyjechał z ETH, aby objąć posadę w Berlinie. Obu uczonych łączy jednak postać Adolfa Hurwitza, matematyka z ETH. Był on najpierw nauczycielem leniwego studenta Einsteina, a po latach, kiedy fizyk na krótko wrócił do Zurychu, zaprzyjaźnili się i wspólnie muzykowali. Dla Pólyi Hurwitz był mentorem i mistrzem.

Hurwitz „dyryguje” Einsteinem i swoją córką Lisi

Pólya był matematykiem myślącym w kategoriach problemów do rozwiązania, mniej energii wkładał w rozbudowywanie teorii i narzędzi. Słynny problem, który postawił i rozwiązał, dotyczył błądzenia przypadkowego. Wyobraźmy sobie punktową cząstkę, poruszającą się skokami po nieskończonej sieci krystalicznej w taki sposób, że w każdym kroku skacze ona do najbliższego sąsiada w sieci. Przyjmujemy, że prawdopodobieństwo skoku do każdego z sąsiadów jest jednakowe, a poszczególne kroki są niezależne. Dla dwuwymiarowej sieci kwadratowej, prawdopodobieństwo skoku do każdego z sąsiadów jest równe \frac{1}{4}.

Pięć różnych przypadków błądzenia złożonego z ośmiu kroków (Wikimedia)

Można oczywiście rozpatrywać ten proces w sieci d-wymiarowej. Pólya zadał sobie pytanie: Jakie jest prawdopodobieństwo, że błądzący przypadkowo punkt wróci do punktu wyjścia? Podobno problem ten nasunał mu się podczas spaceru po parku, podczas którego aż trzy razy spotkał tego samego studenta z narzeczoną i zaczęło to wygladać niezręcznie, tak jakby śledził młodą parę.

Twierdzenie, które udowodnił Pólya mówi, że cząstka powraca do punktu wyjścia z prawdopodobieństwem równym 1, jeśli wymiar d=1 albo d=2. Natomiast w przypadku wyższych wymiarów powrót jest niepewny i zachodzi z pewnym zależnym od wymiaru prawdopodobieństwem mniejszym niż 1.

Zagadnienie błądzenia przypadkowego bywa formułowane jako problem pijaka, który stawia losowo kroki. Shizuo Kakutani wynik Pólyi sformułował następująco: „Pijany człowiek odnajdzie drogę do domu, lecz pijany ptak może zabłądzić na zawsze”.

Oznaczmy prawdopodobieństwo powrotu przynajmniej raz przez s. Można je powiązać z prawdopodobieństwami P_{2n} znalezienia się cząstki w punkcie wyjścia po zrobieniu 2n kroków (po zrobieniu nieparzystej liczby kroków nie może ona znaleźć się w punkcie wyjścia). Okazuje się, że

s<1 \Leftrightarrow \displaystyle \sum_{n=1}^{\infty} P_{2n}<\infty.

(Dowód przedstawiamy na końcu wpisu.) Zbadajmy więc, jak zachowuje się ciąg P_{2n}. W przypadku d=1 każdy krok ma długość 1 i z prawdopodobieństwem \frac{1}{2} cząstka robi krok w lewo bądź w prawo. Powrót do punktu wyjścia po 2n krokach oznacza, że cząstka wykonała n kroków w prawo i tyle samo w lewo. Liczba możliwości wynosi tu {2n \choose n}. Prawdopodobieństwo jest więc równe

\displaystyle P_{2n}={2n \choose n}\dfrac{1}{2^n}\sim \dfrac{1}{\sqrt{\pi n}}.

Ostatnie oszacowanie słuszne jest dla dużych wartości n (Por. Skąd się wzięła liczba pi… albo Czemu rozkład Gaussa…). Szereg o wyrazie ogólnym 1/\sqrt{n} jest rozbieżny (podobnie jak całka \displaystyle \int_{1}^{\infty} \!\!\frac{dx}{\sqrt{x}} ).

Zobaczmy, jak to wygląda w przypadku d=2. Kroki wykonywane przez naszą cząstkę to (0,1), (0,-1), (1,0), (-1,0). Jeśli obrócić układ współrzędnych o 45^{\circ}, możemy doprowadzić do sytuacji, w której kroki równe są (1,1), (-1,-1), (1,-1), (-1,1) (długość kroków jest i tak umowna). Teraz widać, że mamy do czynienia z dwoma niezależnymi błądzeniami przypadkowymi w pierwszej i w drugiej współrzędnej. Obie współrzędne powinny wrócić do zera, aby cząstka wróciła do początku współrzędnych. Prawdopodobieństwo, że jedna oraz druga wrócą po 2n krokach jest teraz równe iloczynowi prawdopodobieństw dla każdej ze współrzędnych:

\displaystyle P_{2n}=\left({2n \choose n}\dfrac{1}{2^n}\right)^2 \sim \dfrac{1}{\pi n}.

Szereg o wyrazie ogólnym 1/n jest także rozbieżny; choć niewiele mu brakuje do zbieżności: wystarczyłoby żeby  potęga n była tylko odrobinę większa od 1 (całka jest teraz rozbieżna tylko logarytmicznie). Ostatnia uwaga wskazuje, że zapewne w przypadku d=3 suma P_{2n} okaże się już zbieżna.

Rzeczywiście, można prawdopodobieństwo powrotu zapisać teraz w postaci

P_{2n}=\dfrac{1}{6^{2n}}\displaystyle\sum_{j,k\ge 0, j+k\le n}\dfrac{(2n)!}{(j!k!(n-j-k)!)^2}\le Cn^{-\frac{3}{2}}.

Pokażemy jeszcze związek miedzy prawdopodobieństwem powrotu s, a sumą P_{2n}. Jeśli błądzenie wróciło do początku, to wszystko zaczyna się od nowa. Mamy zatem prawdopodobieństwo s^2, że co najmniej dwa razy błądzenie wróciło do początku i ogólnie s^k, że wróciło co najmniej k razy. Wartość oczekiwana liczby powrotów to \sum_{k=1}^{\infty} s^k. Ta sama wartość oczekiwana jest także równa \sum_{k=1}^{\infty} P_{2n}. Jeśli s<1, obie sumy są skończone; przy s=1 obie są rozbieżne.

Korzystałem m.in. z książek: R. Durretta, Probability. Theory and Examples oraz Joela Spencera, Asymptopia.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s