Błądzenie losowe
Błądzenie losowe – pojęcie z zakresu matematyki i fizyki określające ruch losowy: w kolejnych chwilach czasu cząstka („chodziarz”) przemieszcza się z aktualnego położenia do innego, losowo wybranego. Błądzenie losowe jest przykładem prostego procesu stochastycznego.
Przykładami procesów, które można modelować za pomocą błądzenia losowego są: ruch molekuły w cieczy czy gazie, zmiany ceny wybranego towaru na giełdzie, zmiany finansów gracza w kasynie.
Klasyfikacja procesów błądzenia losowego
Procesy błądzenia losowego można klasyfikować na różne sposoby:
a) procesy proste, będące łańcuchami Markova (prawdopodobieństwo wyboru kolejnego kroku nie zależy od historii ruchu) lub bardziej złożone procesy stochastyczne,
b) procesy na siatkach dyskretnych (np. na siatkach regularnych na prostej, na płaszczyźnie, w przestrzeni, na grafach; w przestrzeniach zakrzywionych) oraz w przestrzeniach ciągłych,
c) procesy zakładające dyskretny czas (zmiana położenia następuje w regularnych odstępach czasu) lub ciągły (zmiana położenia następuje w losowo wybranych odstępach czasu).
Proces dyskretnego błądzenia losowego przechodzi w proces dyfuzji, gdy wielkość skoku w przestrzeni i wielkość skoku czasu zdążają do zera, przy czym jednocześnie wielkość zachowuje stałą wartość (wtedy jest stałą dyfuzji).
Błądzenie na prostej
Najprostszy przykład błądzenia losowego – to ruch po prostej, oparty na następujących założeniach:
- długość kroku cząstki w kolejnych chwilach czasu jest stała
- cząstka z aktualnie zajmowanego punktu przechodzi losowo do jednego z dwóch sąsiednich punktów
- prawdopodobieństwo przejścia jest jednakowe, np. dla przejścia w górę lub w dół prostej pionowej
Średnia z kwadratów odległości, obliczona dla wielu cząstek startujących z tego samego punktu początkowego, po n krokach jest proporcjonalnie do i wynosi gdzie – długość pojedynczego kroku.
Symulacja błądzenia na prostej
Wykresy ruchu ośmiu cząstek otrzymane w symulacji błądzenia losowego.
Cząstki startują w położeniu 0. Na osi poziomej odłożono liczbę n kroków,
na osi pionowej – położenie cząstki x(n) po n krokach.Wykres obok przedstawia wynik symulacji ruchu ośmiu cząstek, błądzących losowo. Cząstki startują z tego samego punktu 0. W każdym kroku dana cząstka może skoczyć do góry lub w dół. Na osi poziomej odłożono numery kolejnych skoków.
Widać, że: a) średnie położenie cząstek po 100 krokach jest równe 0, b) średnia odległość od punktu 0 zwiększa się w miarę ruchu, ale wolniej niż liniowo.
Błądzenia na płaszczyźnie
Wyobraźmy sobie miasto nieskończone, utworzone z ulic tworzących regularną siatkę. Po ulicach porusza się pijak w ten sposób, że na każdym skrzyżowaniu wybiera losowo jedną z czterech dróg (włączając tę, którą przyszedł) i porusza się dalej prosto aż do kolejnego skrzyżowania.
Powyższy przykład obrazuje błądzenie losowe na płaszczyźnie (długość kroku jest jednakowa, punkty wyboru kolejnej drogi tworzą siatkę o współrzędnych całkowitych).
Trajektorie błądzenia losowego
Trajektorie błądzenia losowego o stałych krokach utworzone są z dyskretnych punktów: a) w błądzeniu po prostej punkty te leżą na prostej w równych odległościach od siebie b) dla dwóch wymiarów punkty dyskretne leżą na płaszczyźnie, c) dla trzech wymiarów punkty dyskretne leżą w przestrzeni.
Błądzenie losowe na grafie
Przypuśćmy teraz, że ulice miasta nie tworzą regularnej siatki kwadratowej, ale sieć nieregularną, tak że pijak na skrzyżowaniu może wybrać więc jedną z wielu dróg, każdą z jednakowym prawdopodobieństwem. Np. 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. p. c
Jeden z problemów, jaki rozwiązuje się, brzmi: Czy pijak ma szansę na powrót do domu, który jest w punkcie startu? Okazuje się, że przy pewnych łagodnych założeniach odpowiedź brzmi: tak (podobnie jak dla błądzenia po regularnych siatkach).
Np. jeśli długości ulic między skrzyżowaniami będą 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, iż graf jest planarny – w mieście obok ulic 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 odcinku ulicy pomiędzy skrzyżowaniami. 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 punktu startu 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 zachodzi następujące twierdzenie:
Proces błądzenia losowego na grafie posiada stany chwilowe wtedy i tylko wtedy, gdy opór pomiędzy danym 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.
Zobacz też
Media użyte na tej stronie