Hazarda promenado

Ekzemplo de ok hazardaj promenadoj en unu dimensio komencantaj ĉe 0. La grafikaĵo montras la aktualan pozicion sur la linio (vertikala akso) kontraŭ la tempo-paŝoj (horizontala akso).

Hazarda promenado estas matematika formaligo de trajektorio, kiu konsistas el preni sinsekvajn hazardajn paŝojn. La rezultoj de hazard-promenada analizo estas aplikataj en komputscienco, fiziko, ekologio, ekonomiko kaj kelkaj aliaj kampoj kiel fundamenta modelo por hazardaj procezoj en la tempo. Ekzemple, la vojo sekvata de molekulo, kiam ĝi veturas en likvaĵo aŭ gaso, la serĉa vojo de furaĝbesto, la prezo de variadantaj akcioj kaj la financa statuso de vetludanto povas tute esti modeligataj kiel hazardaj promenadoj. Specifaj kazoj aŭ limoj de hazarda promenado inkluzivas la drinkulan promenadon kaj Lévy-flugon. Hazardaj promenadoj estas rilataj al la modeloj de disvastigo kaj estas fundamenta temo en diskutoj de Markov-procezoj. Kelkaj proprecoj de hazardaj promenadoj, inter kiuj disvastigo-distribuoj, unuatrairejaj tempoj kaj renkontaj indicoj, estas amplekse studitaj. Diversaj diversspecaj hazardaj promenadoj estas de intereso. Ofte, hazardaj promenadoj estas supozataj esti markovaj, sed aliaj, pli komplikaj promenadoj ankaŭ estas de intereso. Iuj hazardaj promenadoj estas sur grafeoj, aliaj sur la rekto, en la ebeno, aŭ en pli altaj dimensioj, dum iuj hazardaj promenadoj estas sur grupoj. Hazardaj promenadoj ankaŭ varias koncerne la tempan parametron. Ofte, la paŝo estas indicita per la naturaj nombroj, kiel en $X_{0},X_{1},X_{2},\dots$. Tamen, iuj promenadoj okupas paŝojn hazard-tempajn, kaj tiuokaze la pozicio $X_{t}$ estas difinita por $t\geq 0$.

Unudimensia hazarda promenado

Speciale elementa kaj konkreta hazarda-promenado estas tiu sur entjeroj $\mathbb {Z}$, kiu komenciĝas ĉe $S_{0}=0$ kaj ĉe ĉiu paŝo moviĝas de $\pm 1$ kun egala probableco. Por difini ĉi tiun promenadon formale, oni prenas sendependajn hazardajn variablojn $Z_{1},Z_{2},\dots$, ĉiu el kiuj estas $1$ kun probableco $1/2$ kaj −1 kun probableco $1/2$, kaj oni difinas $S_{n}:=\sum _{j=1}^{n}Z_{j}.$ Ĉi-tiu sinsekvo $\{S_{n}\}$ estas nomata la simpla hazarda promenado sur $\mathbb {Z}$.

Ĉi tiu promenado povas esti ilustrita jene. Oni supozas, ke oni ĵetas justan moneron. Se ĝi montras kapon, oni moviĝas unu paŝon dekstren sur la nombro-linio. Se ĝi montras la alian flankon, oni moviĝas unu paŝon maldekstren. Do post kvin ĵetoj, oni havas la eblojn esti sur 1, −1, 3, −3, 5, aŭ −5. Oni povas alteriĝi sur 1 ĵetante tri kapojn kaj du vostojn en iu ajn ordo (Notu: "vosto" estu la mala flanko de monerkapo). Estas 10 eblaj vojoj por alteriĝo sur 1. Simile, estas 10 vojoj por alteriĝo sur −1 (ĵetante tri vostojn kaj kaj du kapojn), 5 vojoj por alteriĝo sur 3 (ĵetante kvar kapojn kaj unu voston), 5 vojoj por alteriĝo sur −3 (ĵetante kvar vostojn kaj unu kapon), 1 vojo por alteriĝo sur 5 (ĵetante kvin kapojn), kaj 1 vojo por alteriĝo sur −5 (ĵetante kvin vostojn). Rigardu la suban bildon por ilustraĵo de ĉi-tiu ekzemplo.

Kvin ĵetoj de justa monero

Kion ni povas diri pri la pozicio $S_{n}$ de la promenado post $n$ paŝoj? Kompreneble, estas hazarda, tial ni ne povas kalkuli ĝin. Sed ni povus diri multe pri ĝia distribuo. Ne estas malfacile vidi, ke la atendata valoro $E(S_{n})$ de $S_{n}$ estas nulo. Ekzemple, ĉi tio sekvas de la adiciebleco (j) de ekspekto: $E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0$. Simila kalkulo, uzanta sendependecon de hazardaj variabloj $Z_{n}$, montras, ke $E(S_{n}^{2})=n$. Ĉi tiu sugestas ke $E|S_{n}|$, la atendata distanco de formovo post $n$ paŝoj, devus esti proksimume ${\sqrt {n}}$. Efektive,

$\lim _{n\to \infty }{\frac {E|S_{n}|}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.$

Oni supozas tiri linion malproksime de la origino de la promeno. Kiomfoje la hazarda promenado transiros la linion, se rajtigita daŭri promenante por ĉiam? La sekvonta, eble supriza, teoremo estas la solvo: simpla hazarda promenado $\mathbb {Z}$ transiros ĉiun punkton senliman nombron da fojoj. Ĉi tiu rezulto havas multajn nomojn: la nivelo-transira fenomeno, ripetiĝo aŭ la ruiniĝo de la vetludanto. La kialo por la lasta nomo estas tiel ĉi: se vi estas vetludanto kun limigita monsumo ludanta justan ludon kontraŭ banko kun senlima monsumo, vi sendube malvenkos. La monsumo, kiun vi havas, iniciatos hazardan promenadon kaj ĝi, ĉe iu tempo, atingos 0 kaj la ludo finiĝos. Se $a$ kaj $b$ estas pozitivaj entjeroj, tiam la atendata nombro de paŝoj, ĝis unu-dimensia simpla hazarda promenado startanta el $0$ frapas antaŭe b aŭ −a, estas $a\,b$. La probableco, ke ĉi tiu promenado frapas b antaŭ −a estas $a \over a+b$, kio povas esti derivita de la fakto, ke tiu simpla hazarda promenado estas martingalo.

Iom de la rezultoj supre menciitaj povas esti derivita de proprecoj de Pascal-a triangulo. La nombro de malsamaj promenadoj de $n$ paŝoj, kie ĉiu paŝo estas $+1$ aŭ −1 estas klare $2^{n}$. Por la simpla hazarda-promenado, ĉiu promenado estas egale probabla. Por ke $S_{n}$ egalu nombron $k$, estas necese kaj sufiĉe, ke la nombro de $+1$ en la promenado superu tiun de −1 je $k$. Tiele, la nombro de promenadoj, kiuj kontentigas $S_{n}=k$, estas ĝuste la nombro de vojoj por elekti $(n+k)/2$ elementojn el $n$-elementa aro (por igi ĉi tiun nenula, necesas ke $n+k$ estu para numero), kiu estas ero en Pascal-a triangulo indikita per $n \choose (n+k)/2$. Sekve, la probableco ke $S_{n}=k$ egalas $2^{-n}{n \choose (n+k)/2}$. Reprezentante erojn de Robert-a triangulo per faktorialoj kaj Stirling-a formulo, oni povas akiri bonajn taksojn por ĉi tiuj probabloj por grandaj valoroj de $n$.

Ĉi tiu rilato kun Pascal-a triangulo estas facile montrebla por malgrandaj valoroj de $n$. Ĉe nul ĵetoj oni eltrovas, ke la sola eblo estas resti ĉe nulo. Tamen, ĉe unua ĵeto, oni povas moviĝi al maldekstro aŭ dekstro de nulo, kio signifas, ke estas unu ŝanco de alteriĝo sur −1 kaj unu ŝanco de alteriĝo sur 1. Ĉe dua ĵeto, oni ekzamenas la antaŭan ĵeton. Se oni estis sur 1, oni povas moviĝi sur 2 aŭ poste sur 0. Se oni estis sur −1, oni povas moviĝi sur −2 aŭ poste sur 0. Do ekzistas unu ŝanco de alteriĝo sur −2, du ŝanco de alteriĝo sur 0, kaj unu ŝanco de alteriĝo sur 2.

n	-5	-4	-3	-2	-1	0	1	2	3	4	5
$P[S_{0}=k]$						1
$2P[S_{1}=k]$					1		1
$2^{2}P[S_{2}=k]$				1		2		1
$2^{3}P[S_{3}=k]$			1		3		3		1
$2^{4}P[S_{4}=k]$		1		4		6		4		1
$2^{5}P[S_{5}=k]$	1		5		10		10		5		1

La centra limesa teoremo kaj la leĝo de la ripetata logaritmo priskibas gravajn detalojn pri la simpla hazarda promenado sur $\mathbb {Z}$.

Pli altaj dimensioj

Hazarda promenado en du dimensioj.

Hazarda promenado per pli multaj kaj pli etaj paŝoj. Ĉe la limo, per tre etaj paŝoj, oni atingas Brown-an movadon.

Imagu drinkulon hazarde piedirantan en urbo. La urbo estas senlima kaj aranĝita en kvadrata krado, kaj ĉe ĉiu interkruciĝo, la drinkulo elektas unu el kvar eblaj vojoj (inkluzive de tiu, laŭ kiu li venis) kun egala probableco. Formale, tio ĉi estas hazarda promenado sur la aro de ĉiuj punktoj en la ebeno kun entjero-koordinatoj. Ĉu la drinkulo revenos de la baro al sia hejmo? Oni montris, ke li sukcesos. Ĉi tio estas la plurdimensia ekvivalento de la nivelo-transira problemo diskutita supre. La probableco de reveno al la origino malpliiĝas, se la nombro de dimensioj pliiĝas. En tri dimensioj la probableco malpliiĝis al proksimume 34 %. Derivado, kune kun valoroj de p(d) estas diskutata tie: http://mathworld.wolfram.com/PolyasRandomWalkConstants.html.

La trajektorio de hazarda promenado estas la kolekto de ejoj, kiun ĝi vizitis, konsiderita kiel aro ignorante kiam la promenado atingis tiujn punktojn. En unu dimensio, la trajektorio estas simple la tuto de la punktoj inter la minimuma alto, kiun la promenado atingis, kaj la maksimuma (ambaŭ estas, averanĝe, de la ordo de √n). En pli altaj dimensioj la aro havas interesajn geometriajn proprecojn. Fakte, oni akiras diskretan fraktalon, tio estas aro prezentante ŝajne mem-similecon sur grandaj skaloj, sed sur malgrandaj skaloj oni povas observi "dentemaĵojn", kiuj rezultas el la krado sur kiu la promenado estas elfarata. La du libroj de Lawler, referencitaj sube, estas bona fonto pri ĉi-tiu temo.

Tri hazardaj promenadoj en tri dimensioj.

Hazarda promeno sur grafoj

Ni supozu, ke nun nia urbo jam ne estas perfekta kvadrata krado. Kiam nia drinkulo atingas ia diskruciĝejon, li elektas inter la diversaj haveblaj vojoj kun egala probableco. Tiele, se la diskruciĝejo havas sep elirojn, la alkoholulo iros al ĉiu kun probableco de sepono. Ĉi tio estas hazarda promenado sur grafeo. Ĉu nia alkoholulo atingos sian hejmon? Oni montras, ke je iom mildaj kondiĉoj la respondo ankoraŭ estas jesa. Ekzemple, se la longecoj de ĉiuj bloko estas inter a kaj b (kie a kaj b estas iuj ajn du limigitaj pozitivaj nombroj), tiam la drinkulo, preskaŭ certe, atingos sian hejmon. Rimarku, ke ni ne supozis, ke la grafeo estas ebena, tio estas la urbo povus enhavi tunelojn kaj pontojn. Unu maniero por pruvi ĉi tiun rezulton estas uzado de la konekto al elektraj retoj. Prenu mapon de la urbo kaj loku iun elektran rezistilon sur ĉiu bloko. Nun mezuru la "reziston inter iu punkto kaj senfineco". Alivorte, elektu iujn nombron R kaj prenu ĉiujn punktojn en la elektra reto kun distanco pli granda ol R de nia punkto and kunigu ilin per drato. Ĉi tio nun estas limigita elektra reto kaj ni povus mezuri la reziston de nia punkto al la dratigitaj punktoj. Portu R senfinecen. La limo estas nomata la rezisto inter punkto kaj senfineco. Oni montras, ke la sekvonta estas vera (elementa pruvo troveblas en la libro de Doyle kaj Snell):

Teoremo: grafeo estas transira, se kaj nur se la rezisto inter punkto kaj senfineco estas finia. Ne estas grave, kiu punkto estas elektita, se la grafeo estas konektita.

Vidu ankaŭ

• Brown-a Kliko
• Modelo de Ising

Referencoj

Bibliografio

• David Aldous and Jim Fill, Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/users/aldous/RWG/book.html Arkivigite je 2004-09-21 per la retarkivo Wayback Machine
• Doyle, Peter G.; Snell, J. Laurie (1984), Random walks and electric networks, Carus Mathematical Monographs, 22, Mathematical Association of America, (ISBN 978-0-88385-024-4), MathSciNet920811, http://arxiv.org/abs/math.PR/0001057 
• William Feller (1968), An Introduction to Probability Theory and its Applications (Volume 1). ISBN 0-471-25708-7

Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.

• Barry D. Hughes (1996), Random walks and random environments, Oxford University Press. ISBN 0-19-853789-1
• Gregory Lawler (1996), Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X
• Gregory Lawler, Conformally Invariant Processes in the Plane, http://www.math.cornell.edu/~lawler/book.ps
• Neal Madras and Gordon Slade (1996), The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1
• James Norris (1998), Markov Chains, Cambridge University Press. ISBN 0-521-63396-6
• Springer Pólya (1921), "Über eine Aufgabe der Wahrscheinlichkeitstheorie betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1-2):149–160, March 1921.

• Robin Pemantle (2007), A survey of random processes with reinforcement.

• Pal Révész (1990), Random walk in random and non-random environments, World Scientific Pub Co. ISBN 981-02-0237-7
• Wolfgang Woess (2000), Random walks on infinite graphs and groups, Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3
• The XScreenSaver has a hack wander that shows random walk on the plane with the color changing with time.
• Mackenzie, Dana, "Taking the Measure of the Wildest Dance on Earth", Science, Vol. 290, 8 December 2000.
• "Numb3rs Blog." Department of Mathematics. 29 April 2006. Northeastern University. 12 December 2007 http://www.atsweb.neu.edu/math/cp/blog/?id=137&month=04&year=2006&date=2006-04-29 Arkivigite je 2007-02-06 per la retarkivo Wayback Machine.

Eksteraj ligiloj

• Pólya's Random Walk Constants
• Javascript builds a distribution from 50 step walks
• Random walk in Java Applet Arkivigite je 2007-08-31 per la retarkivo Wayback Machine
• Random Walk Java Applet 2 Arkivigite je 2009-04-16 per la retarkivo Wayback Machine
• Numb3rs Blog