Błądzenie przypadkowe

Projekt zaliczeniowy kursu: Mathematica I: kurs wstępny
Paweł Nowak
Fizyka doświadczalna III rok
Wydział Fizyki, Astronomii i Informtyki Stosowanej
Uniwersytet Jagielloński
Kraków 2009

Zawartość projektu

Spis treści:

1. Zawartość projektu 				s2
2. Zadanie 					s3
2.1. Trochę teorii 				s3
3. Spacer po prostej 				s4
4. Błądzenie przypadkowe po okręgu		s5
5. Spacer po kracie 				s6
6. Spacer dwuwymiarowy 			s7
7. Spacer po kracie 				s8 
8. Spacer3D 					s9 
8.1. Błądzenie po kuli 				s9 
9. Błądzenie po torusie 			s10 
10. Błądzenie po wstędze Moebiusa 		s11 
11. Podsumownie 				s12 
12. Literatura 					s13

Zadanie

Pijak wyszedł z baru; jest ciemna i zimna noc, ziemia jest płaska lub okragła, droga jest prosta lub krzywa a pijak chce trafić do domu.
Ropatrzmy problem klasycznie, tzn. jak będzie wygladał spacer pijaka? Dojdzie do domu czy może nigdy nie odejdzie od baru? Zakładamy, że każdy jego krok jest zupełnie przypadkowy. W Notebooku pokazuję co stanie się, gdy pijak będzie błądził po różnych krzywych oraz jak będzie wyglądać jego droga i jaką pokona odległość.

Trochę teorii

Błądzenie losowe jest procesem, w którym startując z określonego punktu wykonujemy sekwencję kroków określonej długości, za każdym razem zanim  wykonamy krok losujemy kierunek, każdy kolejny krok jest niezależny od poprzedniego, żaden z kierunek nie jest wyróżniony.
Błądzenie jest abstrakcją w odniesieniu do zakresu procesów obserwowanych w różnego rodzaju naturalnych systemach złożonych.

Przykładem błądzenia losowego w naturze mogą być ruchy Browna; chaotyczne ruchy cząsteczek, pyłów, zawiesin w cieczy lub w gazie spowodowane ciągłym ruchem cieplnym atomów cieczy lub gazu. Równie dobrym przykładem jest dyfuzja różnych substancjach. W biologii obserwujemy migracje żerujących owadów, na giełdzie wahania cen akcji lub sytuację finansową gracza. Również dla tych procesów możemy budować modele błądzenia przypadkowego. 
Analiza błądzenia losowego znalazła zastosowanie w wielu dziedzinach informatyki, fizyki, ekologii, ekonomii, psychologii... Są one podstawowym tematem dyskusji w procesach Markowa. Zastosowań jest jest bardzo wiele, kilka z nich znajdziecie MouseOver.
Rekiny ,,poszły'' krok dalej i zastosowały Lévy flight. Kiedy rekinom zabraknie pokarmu w danym miejscu, to wówczas zmieniają swój ruch typu Browna na sekwencje długich i krótkich ruchów.
 
 
 Z rozważań nad błądzeniem na prostej wynika że średnia odległość Dsr(N) po N krokach wyniesie:

Dsr[N_]==(Sqrt[N])±(1/2)(Sqrt[N])

Zatem sprawdźmy czy tak jest.

Błądzenie przypadkowe w jednym wymiarze

Zaczniemy od analizy zadania w jednym wymiarze, np. na prostej:

Spacer po prostej

ClearAll["Global`*"]

lista1d[n_]:=FoldList[Plus,0,(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
lista1d1=lista1d[10000];

ListLinePlot[lista1d1]

ListPlot[lista1d1]

odleglosc[n_]:=(Sqrt[((Last[lista1d[n]])^2)])
n1=100;
odlpo100:=Table[odleglosc[n1],{10000}]

ListPlot[odlpo100]

Histogram[odlpo100]

Dsr=Mean[odlpo100]//N

σ1=StandardDeviation[odlpo100]//N

Zatem średnia odległość jaką przebędzie pijak po 100 krokach będzie równa

Print[Dsr±σ1]

Błądzenie przypadkowe po okręgu

ClearAll["Global`*"]

lista1dc[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
lista1dc1=lista1dc[1000];
punkty1dc1[n_]:=Table[{Sin[lista1dc1[[i+1]]],Cos[lista1dc1[[i+1]]]},{i,0,n}];
bladzeniec=ListPlot[punkty1dc1[1000]];
kropki2=Graphics[{Red,PointSize[0.05],Point[{0,1}],Green,PointSize[0.05],Point[{Sin[Last[lista1dc1]],Cos[Last[lista1dc1]]}]}];
Show[bladzeniec,kropki2]

nokrazen=Table[Last[lista1dc[1000]/(2Pi)],{1000}];
odlpo1000k:=Table[Last[lista1dc[1000]],{1000}];

ListPlot[odlpo1000k]

ListPlot[nokrazen]

Histogram[nokrazen]

Histogram[odlpo1000k]

Błądzenie dwuwymiarowe

Spacer po kracie

Spacer po kracie to spacer podczas którego nasz pijak wybiera jeden z czterech kierunków, niezależnie od tego jak je nazwiemy, czy wschód, zachód, północ, południe czy powiemy że poruszać się będzie do przodu, do tyłu, na prawo, na lewo, ważne jest by każdy z losowanych kierunków był równie prawdopodobny.

ClearAll["Global`*"]

lista2dk[n_]:=Module[{kierunki={{0,1},{1,0},{0,-1},{-1,0}}},FoldList[Plus,{0,0},kierunki[[RandomInteger[{1,4},n]]]]]
krata2d100=lista2dk[1000];

Histogram3D[krata2d100]

kropki3=Graphics[{Red,PointSize[0.05],Point[{0,0}],Green,PointSize[0.05],Point[Last[krata2d100]]}];
Show[Graphics[Line[krata2d100],Axes->Automatic,AspectRatio->Automatic],kropki3]

drogapoke[n_]:=√(((First[Last[lista2dk[n]]])^2)+((Last[Last[lista2dk[n]]])^2))
drogapoke100=Table[drogapoke[100],{1000}];

ListPlot[drogapoke100]

Dsr2=Mean[drogapoke100]//N;
σ2=StandardDeviation[drogapoke100]//N;

Zatem średnia odleglość jaką przebędzie pijak po 100 krokach po kracie będzie równa

Print[Dsr2±σ2]

Histogram[drogapoke100]

Spacer dwuwymiarowy

Spacer ten odbywa się na płaszczyźnie Euklidesa. Możemy przypuszczać, że pijak podobnie poruszałby się po lotnisku lub na prostej szerokiej drodze.

ClearAll["Global`*"]

r=1;
spacer2D[n_]:=FoldList[Plus,{0,0},({r Cos[#1],r Sin[#1]}&)/@RandomReal[{0,2 π},n]]
lista2d100=spacer2D[1000];

Histogram3D[lista2d100]

kropki2d4=Graphics[{Red,PointSize[0.05],Point[{0,0}],Green,PointSize[0.05],Point[Last[lista2d100]]}];

bladzenie2d=Graphics[Line[lista2d100],Axes->Automatic,AspectRatio->Automatic];

Show[bladzenie2d,kropki2d4]

drogapo2d[n_]:=√(((First[Last[spacer2D[n]]])^2)+((Last[Last[spacer2D[n]]])^2))
drogapo2d100=Table[drogapo2d[100],{10000}];

ListPlot[drogapo2d100]

Dsr3=Mean[drogapo2d100]//N;
σ3=StandardDeviation[drogapo2d100]//N;

Zatem średnia odleglość jaką przebędzie pijak po 100 krokach na płaszczyźnie będzie równa

Print[Dsr3±σ3]

Histogram[drogapo2d100]

Błądzenie w 3 wymiarach

Spacer po kracie

Krata 3D mogłaby być wyzwaniem dla nie jednego alpinisty co dopiero dla naszego bohatera, jednakże eksperyment w Mathematice jest jak najbardziej bezpieczny.
Spacer po kracie 3D wymaga już wybrania nie jednego z 4, ale jednego z 6 kierunków.

ClearAll["Global`*"]

lista3dk[n_]:=Module[{kierunki={{0,1,0},{1,0,0},{0,0,1},{0,-1,0},{-1,0,0},{0,0,-1}}},FoldList[Plus,{0,0,0},kierunki[[RandomInteger[{1,6},n]]]]]
krata3d100=lista3dk[1000];
kropki3dkr=Graphics3D[{Red,PointSize[0.05],Point[First[krata3d100]],Green,PointSize[0.05],Point[Last[krata3d100]]}];

Show[Graphics3D[Line[krata3d100],Axes->Automatic,AspectRatio->Automatic],kropki3dkr]

drogapok3[n_]:=√(((First[Last[lista3dk[n]]])^2)+Last[lista3dk[n]][[2]]^2+((Last[Last[lista3dk[n]]])^2))

drogapok3100=Table[drogapok3[100],{1000}];

ListPlot[drogapok3100]

Dsr4=Mean[drogapok3100]//N;
σ4=StandardDeviation[drogapok3100]//N;

Zatem średnia odleglość jaką przebędzie pijak po 100 krokach po kracie będzie równa

Print[Dsr4±σ4]

Histogram[drogapok3100]

Spacer 3D

ClearAll["Global`*"]

(* n – liczba kroków *)
(* d – wymiar przestrzeni *)bladzeniend[n_,d_]:=NestList[(#+(-1)^Table[Random[Integer],{d}])&,Table[0,{d}],n]
bladzenie3d[n_]:=NestList[(#+(-1)^Table[Random[Integer],{3}])&,Table[0,{3}],n]
bladzenie3d1000=bladzenie3d[1000];

Graphics3D[{RGBColor[0,1,0], PointSize[.02], Point[First[bladzenie3d1000]],RGBColor[1,0,0], PointSize[.02],Point[Last[bladzenie3d1000]],Black ,Line[bladzenie3d1000]},Axes->Automatic,AspectRatio->Automatic]

Spacer po powierzchni

Błądzenie po kuli

Spacer po kuli to spacer po jej powierzchni wzdłuż południków i równoleżników.

ClearAll["Global`*"]

kula=ParametricPlot3D[{ Cos[t] Cos[u], Sin[t] Cos[u], Sin[u]},{t,0,2Pi},{u,-Pi/2,Pi/2},PlotStyle->FaceForm[Black],Mesh->None];
spacern3a[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
spacern3b[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
l3a1=spacern3a[10000];
l3a2=spacern3b[10000];
punktyn3ab[n_]:=Table[{Cos[l3a2[[i+1]]]Cos[l3a1[[i+1]]],Sin[l3a1[[i+1]]]Cos[l3a2[[i+1]]],Sin[l3a2[[i+1]]]},{i,0,n}];
punktyn3ab100=punktyn3ab[10000];
blpok=Graphics3D[{RGBColor[0,1,0], PointSize[.02], Point[First[punktyn3ab100]],RGBColor[1,0,0], PointSize[.02],Point[Last[punktyn3ab100]],White ,Line[punktyn3ab100]},Axes->Automatic,AspectRatio->Automatic];

Show[blpok,kula]

Błądzenie po torusie

Powierzchnią z jaką przyjdzie się nam zmierzyć będzie powierzchnia torusa, której bardzo dobrym wyobrażeniem jest powierzchnia obwarzanka.

ClearAll["Global`*"]

torus[c_,a_]:=ParametricPlot3D[{(c+a Cos[v])Cos[u],(c+a Cos[v])Sin[u],a Sin[v]},{v,0,2Pi},{u,0,2Pi},PlotStyle->FaceForm[Yellow,Blue],Mesh->None];
spacern3at[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
spacern3bt[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
l3a1t=spacern3at[10000];
l3a2t=spacern3bt[10000];
punkty3tor[n_,c_,a_]:=Table[{(c+a Cos[l3a2t[[i+1]]])Cos[l3a1t[[i+1]]],Sin[l3a1t[[i+1]]](c+a Cos[l3a2t[[i+1]]]),a Sin[l3a2t[[i+1]]]},{i,0,n}];
punkty3tor100=punkty3tor[10000,10,2];
blpot=Graphics3D[{RGBColor[0,1,0], PointSize[.02], Point[First[punkty3tor100]],RGBColor[1,0,0], PointSize[.02],Point[Last[punkty3tor100]],Green ,Line[punkty3tor100]},Axes->Automatic,AspectRatio->Automatic];

Show[blpot,torus[10,2]]

Błądzenie po  wstędze Möbiusa

Samo istnienie wstęgi Möbiusa obiektu zwanego dwuwymiarową zwartą rozmaitością topologiczną, posiadającego jedną krawędź i jedną stronę jest czymś niezwykłym. Czym zatem będzie spacer po takiej rozmaitości? Zobaczcie poniżej.

ClearAll["Global`*"]

Moebius[R_,s_,t_]:={(R+s Cos[t/2])Cos[t],(R+s Cos[t/2])Sin[t],s Sin[t/2]}
wstegam[r_,w_]:=ParametricPlot3D[Moebius[r,s,t],{s,-w,w},{t,0,2π},Mesh->None];

Manipulate[ParametricPlot3D[Moebius[r,s,t],{s,-w,w},{t,0,2π},Mesh->None],{r,1,10,1},{w,0.1,5,.1}]

Błądzenie o zmiennym kroku

spacern3m1[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
l3mb1=spacern3m1[1000];
l3mb1=spacern3m1[1000];
spacern3m1c[n_,c_]:=Block[{count,j,k,rn,l=n+1},Table[
count=l;
j=c;
k=0;
rn={-1,0,1};
Do[{If[ Abs[k]<j,k=k+RandomChoice[rn]j/10,count++],If[k==-j,k=k+j/10 RandomChoice[rn],count++],If[k==j,k=k+j/10 RandomChoice[rn],count++]},{count}];
{k,0},{l}]]
punktyspc5=spacern3m1c[1000,.5];
punkty3mob[n_,a_]:=Table[Moebius[a,punktyspc5[[i+1,1]],l3mb1[[i+1]]],{i,0,n}];
punkty3mob100=punkty3mob[1000,2];

Graphics3D[{RGBColor[0,1,0], PointSize[.02], Point[First[punkty3mob100]],RGBColor[1,0,0], PointSize[.02],Point[Last[punkty3mob100]],Green ,Line[punkty3mob100]},Axes->Automatic,AspectRatio->Automatic]

ListPlot[punktyspc5,AspectRatio->Automatic,PlotRange->{{Min[punktyspc5],Max[punktyspc5]},{-0.10,0.1}},PlotMarkers->{Automatic,12}]

Błądzenie o stałym kroku

spacern3m2[n_]:=FoldList[Plus,0,Pi/12(Sign[Sin[#1]] Sign[Cos[#1]]&)/@RandomReal[{0,2 π},n]];
l3mb2=spacern3m2[10000];

pnorm=Table[punkty3mob100[[n]]/Sqrt[punkty3mob100[[n,1]]^2+punkty3mob100[[n,2]]^2+punkty3mob100[[n,3]]^2],{n,1,1001}];

Graphics3D[{Red, PointSize[.02], Point[First[pnorm]],Blue, PointSize[.02],Point[Last[pnorm]],Green ,Line[pnorm]},Axes->Automatic,AspectRatio->Automatic]

Podsumowanie

Nasz pijak zapewne doszedł już do domu, może nie miał tylu wrażeń ile doświadczyłby mu spacery po naszych rozmaitościach, ale na pewno dotarł cało i zdrowo. Badając średnią drogę, możemy zauważyć, że jej wartość jest zbliżona do wartości teoretycznej. Zatem otrzymaliśmy satysfakcjonujące wyniki. Zainteresowaych zachęcam do dalszej lektury i polecam Literaturę.

Literatura

Feynman R.P.,  Leighton R. B.,  Sands M. ,,Feymana Wykłady z Fizykii" tom 1, Część1, ss. 95-103

Kotowski Marcin ,,Kwantowe błądzenia losowe"
http://skfiz.wdfiles.com/local--files/brenna-2010/Marcin Kotowski - Brenna 2010.pdf

Feller W. (1966) Wstęp do rachunku prawdopodobieństwa, Tom I, Warszawa, PWN

Wagenaar W.A. (1988) Paradoxes of Gambling Behaviour

Thomas J.A. (1991) Elements of Information Theory, New York
http://www.elementsofinformationtheory.com/

"Shark uses Levi Fligth"
http://physicsworld.com/cws/article/news/42899

"VLAB random-walk"
http://vlab.infotech.monash.edu.au/simulations/swarms/random-walk

http:// en.wikipedia.org/wiki/Random_walk # Applications

http://mathworld.wolfram.com/RandomWalk1-Dimensional.html

http://mathworld.wolfram.com/RandomWalk2-Dimensional.html

http://mathworld.wolfram.com/RandomWalk3-Dimensional.html