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
.
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 .
Przykład
|
Przykład błądzenia losowego |
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.
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
.
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.
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.