Błądzenie losowe
Z Wikipedii
Błądzenie losowe to pojęcie z zakresu matematyki i fizyki określające sformalizowane przedstawienie procesu, polegającego na podejmowaniu kolejnych kroków, każdy w losowo wybranym kierunku. Błądzenie losowe jest przykładem prostego procesu stochastycznego.
Spis treści |
[edytuj] Własności
Najprostszy przykład błądzenia losowego to ścieżka skonstruowana według następujących zasad:
- Istnieje punkt początkowy
- Odległość od jednego punktu ścieżki do następnego jest stała
- Kierunek od jednego punktu ścieżki do drugiego jest wybierany losowo i żaden z kierunków nie jest bardziej prawdopodobny od drugiego
Średnia odległość w linii prostej pomiędzy punktem początkowym i punktem końcowym po n krokach rośnie zgodnie z 
. Jeśli przez "średnią" będziemy rozumieć średnią kwadratową, wtedy średnia odległość po n krokach wyniesie dokładnie .
[edytuj] Przykład
Wykres (n,R(n)) ośmiu różnych symulacji błądzenia losowego zaczynających się w 0.
Wykres przedstawia osiem przykładów błądzenia losowego, każdy o długości 100 kroków. W każdym kroku proces może pójść do góry lub na dół. Można zauważyć, że pozostają one skupione wokół punktu początkowego, a średnia odległość od tego punktu zwiększa się, ale wolniej niż liniowo.
[edytuj] Większa liczba wymiarów
Wyobraźmy sobie pijaka spacerującego po mieście. Miasto jest nieskończone i całkowicie uporządkowane, a na każdym skrzyżowaniu pijak ma do wyboru jedną z czterech dróg (włączając tę, którą przyszedł). Formalnie jest to proces błądzenia losowego na płaszczyźnie o całkowitych współrzędnych. Czy pijak kiedykolwiek wróci z baru do domu? Okazuje się, że prawdopodobieństwo powrotu pijaka do domu wynosi 1 (!) – matematycy mówią w takiej sytuacji: prawie na pewno. Jest to wielowymiarowa wersja problemu przekraczania poziomu, opisanego wcześniej. Jednak podobieństwa na tym się kończą. W trzech i więcej wymiarach to twierdzenie nie jest prawdziwe. Innymi słowy, pijany ptak mógłby zawsze błądzić w przestrzeni, nigdy nie trafiając do swojego gniazda. Opisując rzecz formalnie, błądzenie losowe w 1 i 2 wymiarach jest procesem stochastycznym ze stanami powtarzającymi się, natomiast błądzenie losowe w 3 wymiarach to proces o stanach chwilowych. Udowodnił to w 1921 roku George Polya.
Trajektoria błądzenia losowego to kolekcja miejsc odwiedzonych przez proces, rozważana jako zbiór bez brania pod uwagę kiedy proces osiągnął dany punkt. W jednowymiarowej przestrzeni trajektoria to po prostu wszystkie punkty pomiędzy minimalną wysokością osiągniętą przez proces a maksymalną wysokością (obie rosną średnio zgodnie z ). Przy większej liczbie wymiarów dostajemy dyskretny fraktal, to znaczy zbiór, który w dużej skali wykazuje własność samopodobieństwa, ale w mniejszej skali zobaczymy wpływ siatki, na której odbywa się proces.
[edytuj] Błądzenie losowe na grafie
Przypuśćmy teraz, że nasze miasto nie jest uporządkowane. Kiedy pijak dociera do skrzyżowania, może wybrać jedną z wielu dróg, każdą z jednakowym prawdopodobieństwem. Jeśli ze skrzyżowania wybiega siedem dróg, pijak wybierze każdą z nich z prawdopodobieństwem 1/7. Taki problem nazywamy błądzeniem losowym na grafie. Czy nasz pijak ciągle ma szansę na powrót do domu? Okazuje się, że przy pewnych łagodnych założeniach odpowiedź ciągle brzmi: tak. Na przykład jeśli długość wszystkich bloków pozostanie w przedziale od 10 metrów do 10 kilometrów (albo pomiędzy dwoma innymi dowolnymi liczbami), wtedy pijak prawie na pewno dotrze do domu. Ciekawe jest, że nie zakładamy przy tym, że graf jest planarny, tzn. że w mieście mogą być tunele i mosty. Jeden z dowodów opiera się na związkach z sieciami elektrycznymi. Weźmy mapę miasta i umieśćmy rezystor na każdym bloku. Teraz zmierzmy "opór pomiędzy danym punktem a nieskończonością". Innymi słowy, wybierzmy liczbę R i weźmy wszystkie punkty w sieci elektrycznej odległe o więcej niż R od naszego punktu i połączmy je razem. Mamy skończoną sieć elektryczną i jesteśmy w stanie zmierzyć opór od naszego punktu do połączonych punktów. Zwiększajmy R do nieskończoności. Granicę nazwiemy oporem pomiędzy punktem i nieskończonością. Okazuje się, że prawdą jest:
Twierdzenie: proces błądzenia losowego na grafie posiada stany chwilowe wtedy i tylko wtedy, gdy opór pomiędzy punktem i nieskończonością jest skończony. Nie jest ważne, jaki punkt wybierzemy.
Okazuje się, że taki opis procesów ze stanami chwilowymi i powtarzającymi się jest bardzo wygodny i w szczególnym przypadku pozwala na analizę przypadku miasta na płaszczyźnie z ograniczonymi odległościami.
Nie należy mylić błądzenia losowego na grafie z łańcuchem Markowa. W przeciwieństwie do łańcuchów Markowa, błądzenie losowe na grafie posiada własność symetrii względem czasu lub odwracalności. Oznacza to mniej więcej, że prawdopodobieństwa przejścia danej trasy w jednym lub drugim kierunku są ze sobą w prosty sposób powiązane (jeśli graf jest regularny są po prostu równe). Okazuje się, że ta własność pociąga za sobą ważne konsekwencje.
