Spacerowanie pijana
Stanąć w pozycji 0 na linii liczbowej. W każdym ułamku sekundy rzuć monetą: orłem oznacza przesunięcie się w prawo, reszką – w lewo. To stanowi całe, najprostsze możliwe losowe przejście, a jednak leży ono u podstaw zjawisk tak różnych jak drganie pyłków w wodzie, rozprzestrzenianie się cząsteczek gazu przez pokój oraz dzienna ścieżka ceny akcji. Prosta natura tego przejścia sprawia, że jest ono niezwykle potężne – niezależnie od tego, co dokładnie reprezentuje "krok", stosuje się tę samą niewielką liczbę faktów statystycznych.
Dlaczego √t, a nie t
Po n krokach ±1 pozycja jest sumą n niezależnych losowych znaków. Oczekiwana pozycja wynosi dokładnie zero – zarówno kroki dodatnie, jak i ujemne średnio się zniwelują – ale wariancja zachowuje się zupełnie inaczej niż oczekiwana: dla niezależnych zmiennych losowych wariancje po prostu sumują się. Ten jeden fakt napędza całą dziedzinę.
X_n = S1 + S2 + ... + Sn // każdy Si = +1 lub -1, równa prawdopodobieństwo Wartość oczekiwana E[X_n] = 0 // oczekiwana pozycja: z powrotem do początku Wariancja Var(X_n) = n // wariancja rośnie liniowo wraz z krokami Odchylenie standardowe sigma(X_n) = sqrt(n) // typowe przesunięcie rośnie jako sqrt(n) // Po 1 000 000 krokach: zazwyczaj tylko ~1 000 kroków od początku Zgodnie z twierdzeniem o rozkładzie normalnym, rozkład X_n zbiega się do rozkładu Gaussa, X_n ~ N(0, n), nawet jeśli każdy indywidualny krok to rzut monetą bez żadnej krzywej symetrii – imponująca regularność wyłaniająca się z czystej losowości. Zmniejsz kroki i interwały czasowe razem, zachowując tę skalę, a dyskretna wędrówka staje się ciągłym ruchem Browna, którego średni kwadrat przesunięcia ⟨r²⟩ = 2dDt (d = wymiary, D = współczynnik dyfuzji) – wynik Einsteina z 1905 roku, później potwierdzony eksperymentalnie przez Jeana Perrina, który dostarczył jedno z pierwszych twardych dowodów na to, że atomy są rzeczywiste.
X_n = S1 + S2 + ... + Sn // each Si = +1 or -1, equal probability E[X_n] = 0 // expected position: back at the origin Var(X_n) = n // variance grows LINEARLY with steps sigma(X_n) = sqrt(n) // typical displacement grows as sqrt(n) // After 1,000,000 steps: typically only ~1,000 steps from the start
Równanie dyfuzji to przypadkowy spacer w przebraniu
Weź rozkład prawdopodobieństwa pozycji losowego chodźca i pozwól, aby liczba kroków rosła do dużej wartości; przestrzega ono tego samego równania różniczkowego częściowego, jak ciepło przepływające przez ciało stałe lub farba rozpuszczająca się w wodzie:
dP/dt = D * d2P/dx2 // równanie dyfuzji (cieplnego) P(x, t) = 1/sqrt(4*PI*D*t) * exp(-x^2 / (4*D*t)) // rozwiązanie punktowe // Rozkład normalny, który się rozszerza jak sqrt(t) -- to samo skalowanie sqrt(n), ponownie Zgodność działa w obie strony w praktyce: fizycy rozwiązują równanie cieplne numerycznie symulującymi skupiska niezależnych losowych chodźców (metodę Monte Carlo), a odwrotnie obliczają statystyki chodzenia, rozwiązując to równanie różniczkowe bezpośrednio – dwa spojrzenia na ten sam podstawowy proces.
dP/dt = D * d2P/dx2 // the diffusion (heat) equation P(x, t) = 1/sqrt(4*PI*D*t) * exp(-x^2 / (4*D*t)) // point-source solution // A Gaussian that widens as sqrt(t) -- the same sqrt(n) scaling, again
Powtarzające się w 1D i 2D, przemijające w 3D
Jednym z najbardziej zaskakujących wyników teorii prawdopodobieństwa, dzięki George'owi Póliemu w 1921 roku, jest to, że sama wymiarowość losowego kroku decyduje o tym, czy jest on gwarantowany powrót do punktu wyjścia:
P(w końcu wraca do początku): 1D: P = 1 // powtarzające się – pewny powrotu 2D: P = 1 // powtarzające się – "pijak zawsze znajduje drogę" 3D: P ≈ 0,3405 // przemijające – "ptaszek pijak może zostać na zawsze zgubiony" 4D+: P -> 0 // prawie nigdy nie wraca Próg w dwóch wymiarach ma realne konsekwencje fizyczne: dwa rozpuszczające się defekty ograniczone do powierzchni 2D są matematycznie gwarantowane, że ostatecznie zderzą się i mogą reagować lub anihilować, podczas gdy te same cząstki rozprzestrzeniające się swobodnie w 3D przestrzeni mogą – i często robią – na stałe oddalić się od siebie, co wyjaśnia, dlaczego reakcje ograniczone do dyfuzji zachowują się jakościowo inaczej w błonie niż w cieczy masowej. Inna, choć powiązana, wersja to samoodparowy krok, który nigdy nie może odwiedzić miejsca, które już zajęło – standardowy model łańcucha polimerowego w roztworze, którego odległość między końcami rośnie jako n^ν z wykładnikiem Flory ν ≈ 0,588 w 3D, a nie 0,5 zwykłego, niezwiązanego kroku.
P(eventually returns to origin): 1D: P = 1 // recurrent -- certain to return 2D: P = 1 // recurrent -- "a drunk always finds home" 3D: P ≈ 0.3405 // transient -- "a drunk bird may be lost forever" 4D+: P -> 0 // almost never returns
Loty Levisa, siatki i gdzie model się wygina
Rzeczywiste "losowe chodzenie" rzadko wybiera kroki z ładnego, ograniczanego rozkładu. Chodź lewitujący w siatce ogranicza kroki do dyskretnych kierunków siatki — klasyczny model dla rozpraszającego się gazu lub naiwny algorytm rozwiązywania labiryntów. Zamiast tego lot Levisa pobiera długości kroków z prawykonującego prawo rozkładu o dużym ciężarze: głównie krótkie lokalne skoki, sporadycznie przerywane bardzo długim skokiem. Ta mieszanka została zaobserwowana w ścieżkach polowań albatrosów i rekinów polujących na rzadkie, nieprzewidywalnie rozmieszczone zdobyczne, a okazuje się, że jest bliska optymalnej strategii wyszukiwania pod względem matematycznym, gdy cele są rzadkie i losowo rozrzucone — naprawdę inny reżim skalowania niż uporządkowany √t prawodawstwa losowych chodzeń Gaussa.
Rynki finansowe to najistotniejsze miejsce, w którym czysty model losowego chodzenia ulega zawrotom. Louis Bachelier modelował ceny akcji jako ruch Brownowski w roku 1900, pięć lat przed Einsteinem, a geometryczny ruch Brownowski nadal leży u podstaw modelu Black-Scholes wyceny opcji — ale prawdziwe rynki pokazują tłuste ogony (ekstremalne ruchy znacznie częstsze niż przewiduje Gaussa), klastry zmienności i długookresowe korelacje, których prosty losowy chodzenie nie jest w stanie uchwycić, co dokładnie wyjaśnia, dlaczego finanse ilościowe sięgają po procesy Levisa i frakcjonalne ruchy Brownowskie zamiast tego.
Gdzie jeszcze przebiega wędrówka
Algorytm oryginalny PageRank Google modeluje surfera internetowego jako losowego chodźca, który przeskakuje linki; ważność strony jest po prostu prawdopodobieństwem, że chodziciel tam siedzi w stanie równowagi. Metoda Monte Carlo łańcucha Markowa konstruuje losową wędrówkę przez przestrzeń stanów możliwych, tak aby czas spędzony w każdym stanie odpowiadał jego docelowej prawdopodobieństwu, napędzając wszystko od zaawansowanej statystyki Bayesa po symulacje składania białek. Chemotaksja bakterii osiąga kierunkowe ruchy z powodu skośnego losowego chodźca — E. coli zmienia alternatywnie proste "biegi" i losowe „tumbles”, rozszerzając proste biegi, gdy rzeczy się poprawiają wzdłuż gradientu chemicznego. A w obliczeniach kwantowych wędrówka kwantowa jest spójnym analogiem tego wszystkiego: ponieważ amplitudy prawdopodobieństwa mogą interferować zamiast po prostu dodawać, wędrówka kwantowa rozprzestrzenia się jak t zamiast √t, silnik matematyczny stojący za kwadratowym przyspieszeniem w algorytmie wyszukiwania Grovera.
Często zadawane pytania
Dlaczego przesunięcie skaluje się jako √t zamiast t w losowym kroku?
Każdy krok ma niezależną i średnio zerową wartość, co powoduje, że średnie położenie pozostaje przy wyjściu – ale wariancja sumy niezależnych kroków rośnie, dając Var(X_n) = n po n krokach. Odchylenie standardowe jest pierwiastkiem z wariancji, więc typowe przesunięcie rośnie jako √n, a nie n. Spacerzysta, który wykonał milion kroków, zwykle znajduje się tylko około tysiąca kroków od punktu początkowego, a nie miliona.
Dlaczego losowy krok jest gwarantowany do powrotu do punktu wyjścia w 1D i 2D, ale nie w 3D?
Jest to twierdzenie o rekurencji Pólki (1921): prosty losowy krok na 1D lub 2D siatce wraca do punktu początkowego z prawdopodobieństwem 1 przy nieskończonym czasie, co oznacza, że jest rekurencyjny. W trzech lub więcej wymiarach spacerzysta ma zbyt dużo przestrzeni, aby uciec i prawdopodobieństwo powrotu jest ściśle mniejsze niż 1 – około 34% w 3D – co oznacza, że krok jest przejściowy i może wędrować na zawsze. Próg wymiarowy wynosi dokładnie 2.
Jakie jest różnice między losowym krokiem a lotem Levisa?
Zwykły losowy krok pobiera każdą długość kroku z rozkładu o skończonej wariancji, więc przesunięcie zawsze skaluje się jako √t niezależnie od szczegółów. Lot Levisa zamiast tego pobiera długości kroków z rozkładu o ogonie ciężkim (power-law), generując głównie krótkie skoki przerywane sporadycznymi bardzo długimi skokami – ta mieszanka została zaobserwowana w rzeczywistych wzorcach poszukiwania zwierząt, takich jak albatrosy i jest matematycznie zbliżona do optymalnej dla przeszukiwania rzadkich, nieprzewidywalnie rozmieszczonych zasobów.
Wypróbuj na żywo
Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.
▶ Otwórz symulację the simulation