Случајна шетња

Случајна шетња (случајни ход) је математичка формализација пута који се састоји од низа случајних корака. На пример, путања праћења молекула као што путује у течност или гас, за претрагу пута сакупљањем животиње, цена једне променљиве акције и финансијски статус коцкара могу се моделирати као случајне шетње, иако то не може бити истински случајно у стварности. Термин случајног хода је први пут уведео Карл Пеарсон 1905. Случајне шетње су коришћене у многим областима: екологија, економија, психологија, информатика, физика, хемија, и биологија. Случајне шетње објашњавају уочена понашања многих процеса у овим областима, и на тај начин служе као темељни модел за снимљене стокестик активности.

Пример осам случајних шетњи у једној димензији са почетком у 0. Парцела показује тренутну позицију на линији (вертикалне осе) у односу на временске интервале (хоризонтална оса).

Различити типови случајних шетњи су од интереса. Често се претпоставља да су Марковљеви ланци или Марковљеви процеси, али и друге, много компликованије шетње су такође од интереса. Неке слободне шетње су на графиконима, друге на линијама, у авиону, у вишим димензијама, или чак заобљеним површинама, док су неке случајне шетње у групама. Слободне шетње такође варирају у односу на временски параметар. Често је шетња у дискретном времену, а потиче из природних бројева, као у к_0, к_1, X_2, \ дотс. Међутим, неке шетње праве своје кораке у случајним размацима, а у том случају положај X_т је дефинисана за бесконачно време т \ ге 0. Одређени случајеви или границе случајних шетњи укључују Леви лет. Случајне шетње су везане за моделе дифузије и представљају основну тему дискусија Марковог рада. Неколико својстава случајних шетњи, укључујући и распростирање дистрибуције, први пролаза времена и сусрет стопа, су интензивно проучавани.

Решетке случајне шетње

Популарни модел случајне шетње је случајна шетња на регуларној решетки, где на сваком кораку локација скаче на друго место, према неким вероватноћама расподеле. У принципу случајне шетње, локација може да скочи само са суседних места решетке, формирајући пут решетке. У једноставној симетричној случајној шетњи на локалном нивоу коначне решетке, вероватноћа за локацију скоковима на сваки његови најближи сусед је иста. Најбољи пример је проучавање случајне шетње на д-димензионални целим решеткама (понекад се назива хиперцубиц решетке) \ матхбб З ^ ум.

Једно димензијална слободна шетња

Основни пример случајне шетње је случајна шетња на цео број линије, \ матхбб З, који почиње у 0 и на сваком кораку креће +1 или -1 са истом вероватноћом.

Ова шетња може се илустровати на следећи начин. Маркер је постављен на нулу на број линије и кованица је преврнута. Ако падне на главу, маркер се помера једну јединицу са десне стране. Ако падне на репове, маркер се помера једну јединицу са леве стране. Након пет бацања, маркер може сада бити на 1, -1, 3, -3, 5 или -5. Са пет бацања, три главе и два репа, у било ком редоследу ће слетети на 1. Постоји 10 начина за слетање на 1 (окретањем три главе и два репа), 10 начина слетања на -1 (окретањем три репа и две главе), 5 начини слетања на 3 (окретањем четири главе и један реп), 5 начине слетања на -3 (окретањем четири репа и једна глава), 1 пут слетању на 5 (окретањем пет глава), и 1 начин слетању на -5 (окретањем пет репа). Погледајте слику испод за илустрацију могућих исхода од 5 окрета.

Сви могући исходи случајних шетњи након 5 бацања новчића

Случајна шетња у две димензије (анимирана везрија)

Случајна шетња у две димензије са 25 хиљада корака (анимирана верзија)

Случајна шетња је дводимензионална са два милиона мањих корака. Ова слика је направљена на такав начин да тачке које су чешће обојене су тамније. У границама, за веома мале кораке, добија се Брауново кретање.

Да бисмо формално дефинисали ову шетњу, узимамо независне случајне променљиве $Z_{1},Z_{2},\dots$, где је свака променљива 1 или -1, са вероватноћом за обе вредности 50% и поставимо $S_{0}=0\,\!$ и $S_{n}=\sum _{j=1}^{n}Z_{j}.$ Серија $\{S_{n}\}\,\!$ се зове једноставно случајна шетња $\mathbb {Z}$. Ова серија (збир секвенци од −1s до 1s) даје удаљеност шетње, ако је сваки део шетње дужина једног. Очекивано $E(S_{n})\,\!$ од $S_{n}\,\!$ је нула. То јест, средња вредност свих бачених новчића приближава се нули како се број бацања повећава. Ово следи од коначних додатака имовине очекивања:

$E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.$

Слична рачуница, користећи независност случајних променљивих и чињеница да $E(Z_{n}^{2})=1$, показује да:

$E(S_{n}^{2})=\sum _{i=1}^{n}\sum _{j=1}^{n}E(Z_{j}Z_{i})=n.$

То наговештава да $E(|S_{n}|)\,\!$, очекивани превод растојања након н корака, треба да буде реда${\sqrt {n}}$. На пример,

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

Овај резултат показује да је дифузија неефикасна за мешање због начина на који се квадратни корен понаша за велико $N$.

Колико пута ће случајна шетња да пређе граничну линију уколико је дозвољено да настави шетњу заувек? Једноставна случајна шетња по \ матхбб З ће прећи сваку тачку неограничен број пута. Овај резултат има много имена: Ниво прелаз феномен, понављање или пропаст коцкар је. Разлог за презиме гласи: коцкар са ограниченом количином новца ће на крају изгубити када играју фер утакмицу против једне банке са бесконачним количином новца. Новац коцкара ће обављати случајну шетњу, а то ће достићи нулу у неком тренутку, и игра ће бити готова.

Ако су а и б позитивни цели бројеви, тада је очекивани број корака до једнодимензионалног принципа случајне шетње са почетком у првим  ударцима  б или -а је АБ. Вероватноћа је да ће ова шетња погодити Б пре него што -а је А / (А + Б), што се може извести из чињенице да једноставна случајна шетња представља лажне узде.

Неки од наведених резултати може бити изведен из својстава Паскаловог троугла. Број различитих слојева н кораке где сваки корак је +1 или -1 је 2н. Из просте случајне шетње, свака од ових шетњи је подједнако вероватна. Да би Сн  био једнак са бројем к потребно је и довољно да број +1 у шетњи премашује оне -1 до к. Број шетњи које задовољавају $S_{n}=k$ је једнак броју начина избора (н - к) / 2 са н које је број дозвољених потеза, означен$n \choose (n-k)/2$. Да ово има значење, потребно је да су н и к парни бројеви. Дакле, вероватноћа да $S_{n}=k$ је једнако . Што представља уносе Паскаловог троугла у смислу факторијала и коришћења Стирлинг формуле, могу се постићи добре процене за ове вероватноће за велике вредности н.

Ако је простор ограничен на \ матхбб З + за краткотрајно, број начина на који ће случајна шетња да слете на сваки број има пет бацања и може да се прикаже као {0,5,0,4,0,1}.

Овај однос са Паскаловим троуглом је доказан за мале вредности н. Ако креће од нуле, једина могућност ће бити да остане на нули. Међутим, у једном опет, постоји једна шанса од слетања на -1 или једно могуће спуштање на 1. У два наврата, маркер на 1 да пређе на 2 или назад на нулу. Маркер на -1, да пређе на -2 или назад на нулу. Дакле, постоји једна шанса од слетања на -2, две шансе за слетање на нулу, а једно могуће слетање на 2.

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

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1

Теорема централне границе и закон понављања логаритма описују важне аспекте понашања принципа случајне шетње \mathbb Z. Конкретно, претходно се подразумева да н расте, приступ вероватноће (пропорционална броју у сваком реду)  са нормалном расподелом.

Као директна генерализација, могу се узети у обзир случајне шетње на кристалној летвици (Инфините износа Абелеви покрива графиконе преко коначних графова). Заправо је могуће успоставити централну граничну теорему и теорему великих девијација у овом окружењу.

Као Марков ланац

Једнодимензионална случајна шетња може се посматрати као Марков ланац чије стање простора је дато по облику целих $i=0,\pm 1,\pm 2,\dots .$ За неке бројеве п задовољава се$\,0<p<1$, вероватноћа прелаза (вероватноћа Пи ј преласка из стања да се наведе ј) и дају:

$\,P_{i,i+1}=p=1-P_{i,i-1}.$

Више димензије

Три случајне шетње у три димензије

Замислите сада пијаница који случајно шета у идеализованом граду. Град је ефективно бесконачан и распоређен у квадратну мрежу, и на сваком пресеку пијанац бира једну од четири могућа пута (укључујући и онај из којег је дошао), са једнаком вероватноћом. Формално, ово је случајна шетња одређена свим тачакама у равни са целим координатама.

Да ли ће се пијанац икада вратити својој кући из бара? То је 2-димензионални еквивалент проблема нивоа прелаза који је раније описан. Испоставило се да је скоро сигурно да ће у 2-димензионалној случајној шетњи, али и са 3 димензије или више, вероватноћа повратка у просеку смањује како се број димензија повећава. У 3 димензије, вероватноћа се смањује за отприлике 34%.

Путања случајне шетње је збир локација које су посећене, које су занемарене док сшетњом не стигнемо на место. У једној димензији, путања су једноставно све тачке између минималне висине шетње која је постигнута и максимално (оба су, у просеку, по налогу √ н). У вишим димензијама скуп има занимљиве геометријске карактеристике. У ствари, један добија дискретни фрактал, то је скуп који показује стохастичко само-сличност на великим скалама, али се у малом обиму може посматрати "јаггеднесс" тако да произилази из мреже на којој се врши шетња. Две Лавлерове књиге наведене у даљем тексту су добар извор за ову тему.

Однос према Винеровом процесу

Главни чланак: Винеров процес

Симулација Винеровог процеса у две димензије

Винеров процес је математичка формулација Брауновог кретања, случајног кретања тела у течностима веће специфичне густине од њега самог.

Винеров процес је повезан са случајном шетњом. Стохастички процес

$W_{n}(t)={\frac {1}{\sqrt {n}}}\sum \limits _{1\leq k\leq \lfloor nt\rfloor }\xi _{k},$

за свако $\xi _{1},\xi _{2},\ldots$, где су то независне и идентични распоређене случајне променљиве са очекиваном вредношћу 0 и варијансом 1, за $n\to \infty$, $W_{n}$ тежи Винеровом процеесу. Конвергенција је дата Централном граничном теоремом. Винеров процес у произвољној димензији је лимес случајне шетње у истој димензији.

Случајна шетња се може посматрати као дискретан фрактал, односно функција целобројних димензија 1, 2, ... Винеров процес је прави фрактал Хаусдорфове димензије 2.

Винеров процес шетње је инваријантан на ротације за произвољни угао, док је случајна шетња инваријантна само на ротације под правим углом, јер је дефинисана на целобројној решетки која сама не поседује инваријантност на остале ротације.

Гаусова случајна шетња

Случајни шетња са бројем корака који варира према нормалној подели се користи као модел за реалне податке временских серија као што су финансијска тржишта. Црна-Сцхолес формула за цену је опција моделирања, на пример, користи Гаусову случајну шетњу као основну претпоставку

Овде, величина корака је инверзна кумулативној нормалној расподели $\Phi ^{-1}(z,\mu ,\sigma )$ где 0 ≤ z ≤ 1је равномерно распоређени случајни број, а μ и σ су средње и стандардне девијације нормалне дистрибуције.

Ако је μ  различит од нуле, случајна шетња ће варирати око линеарног тренда. Обрнуто, ако је почетна вредност случајне шетње, очекивана вредност након н корака ће бити вс + нμ.

За посебан случај где је μ једнака нули, након н корака, расподелом удаљеност је Н (0, нσ2), где је Н ()  ознака за нормалну расподелу, н је број корака, и σ је инверзна кумулативна нормална дистрибуција као што је дато горе.

Доказати: Гаусова случајна шетња може да се посматрати као збир низа независних и идентично дистрибуираних случајних променљивих, Xи из обрнуте кумулативне нормалне дистрибуције са средњом једнаком нули и X  обрнуте кумулативне нормалне дистрибуције:

Z = $\sum _{i=0}^{n}{X_{i}}$,

али имамо дистрибуцију за суму од две независно нормално дистрибуиране случајне променљиве, Z = X + Y, даје

N(μ_X + μ_Y, σ²_X + σ²_Y) (види овде).

У нашем случају, μ_X = μ_Y = 0 и σ²_X = σ²_Y = σ² доноси

N(0, 2σ²)

По индукцији, за н корака имамо

Z ~ N(0, nσ²).

За кораке дистрибуиране према било којој дистрибуцији са нулом на средини и коначне варијансе (не нужно само нормалне дистрибуције), корен средње квадратне удаљеност после н корака је

${\sqrt {E|S_{n}^{2}|}}=\sigma {\sqrt {n}}.$

Али за Гаусову случајну шетњу, ово је само стандардна девијација дистрибуције превода удаљености након н корака. Дакле, ако је μ једнака нули, а од корена значи квадратна (РМС) превод удаљености је једна стандардна девијација, постоји 68,27% вероватноће да ће ефективна удаљеност након н корака пасти између± σ${\sqrt {n}}$. Исто тако, постоји 50% вероватноће да ће  удаљеност након н корака пасти између± 0.6745σ${\sqrt {n}}$.

Аномална дифузија

У поремећеним системима као што су порозна медија и фрактали $\sigma ^{2}$ не може бити пропорционална $t$ али може $t^{2/d_{w}}$. Експонент $d_{w}$се зове експонент аномалије дифузије  и може бити већи или мањи од 2.Аномалоус дифузија се такође може изразити као σ_r² ~ Dt^α где α је параметар аномалније.

Број различитих локација

Број различитих локација које је посетио један случајни шетач $S(t)$ је интензивно проучаван за квадратну и кубну летвицу и за фрактале. Ова количина је корисна за анализу проблема хватања и кинетичких реакција. Такође је у вези са вибрационом густином стања, дифузијом реакције процеса и ширења популације у екологији. Генерализација овог проблема на број различитих локација посетило је $N$ случајних шетача, $S_{N}(t)$, недавно је студирано за Д-димензионалне еуклидске решетке. Број различитих локација посећених од Н шетача у вези су са бројем различитих сајтова које посећује сваки шетач.

Апликације

Антонија Гормлеиа Квантна Облачност скулптура у Лондону дизајниран од стране рачунаром помоћу алгоритма случајне шетње.

Следе неке апликације случајне шетње:

• У финансијској економији,"хипотеза случајна шетња" се користи за моделирање цена акција и других фактора. Емпиријска истраживања пронашла су нека одступања од овог теоријског модела, посебно у кратком року и дугорочним корелацијама. Погледајте цене акција.
• У популационе генетике, слободна шетња описује статистичке особине генетичког дрифта
• У физици, случајне шетње се користе као поједностављени модели физичког Бровновог кретања и дифузије, као што су случајно кретање молекула у течности и гасова. Видети на пример дифузионе ограничене агрегације. Такође у физици, случајне шетње и неке од интеракцији шетње играју улогу у квантној теорији поља.
• У математичкој екологији, случајне шетње се користе да опишу поједине покрете животиња, за емпиријске процесе подршке за биодиффусион, и повремено за моделирање динамике становништва.
• У физици полимера, случајна шетња описује идеалан ланац. То је најједноставнији модел проучавања полимера.
• У осталим областима математике, случајна шетња се користи за израчунавање решења Лапласове једначине, да процени хармоничну меру, и за различите конструкције у анализи и комбинаторици.
• У информатици, случајне шетње се користе за процену величине Веба. У Ворлд Виде Веб конференције 2006. године, бар-Иоссеф и др. објавили су своје налазе и алгоритме за исте.
• У слици сегментације, случајне шетње се користе за утврђивање налепнице (тј "објекат" или "позадина") да се држе сваког пиксела. Овај алгоритам се типично назива алгоритам сегментације случајне шетње.

У свим овим случајевима, случајна шетња је често замењена за Брауново кретање.

• У истраживању мозга, случајне шетње и ојачане случајне шетње се користе за моделирање каскаде неурона које пуцају у мозгу.
• У визији науке, очни заношење тежи да се понаша као случајна шетња. Према неким ауторима, фикатионал покрети ока у целини су такође добро описали случајну шетњу.
• У психологији, случајне шетње објашњавају прецизно однос између времена потребног да се донесе одлука и вероватноће да ће одређена одлука да буде донета.
• Случајне шетње могу се користити за узорковање из државног простора који је непознат или веома велик, на пример, да изабере случајно страну са интернета, или за истраживање услова рада, случајни радник у датој земљи.

Када се овај последњи приступ  користи у компјутерској науци познат је као уметање или МЦМЦ за кратко. Често, узорковање од неког компликованог државног простора такође омогућава да добијете вероватноће процене величине простора екипе. Процена стално велике матрице нуле и јединице је био први велики проблем за решити коришћењем овог приступа.

• Случајне шетње се такође користе за узорковање масивних онлајн графикона као што су они на онлајн друштвеним мрежама.
• У бежичном умрежавању, случајна шетња се користи за моделирање кретања чвора.
• Покретне бактерије које се ангажују у случајној шетњи.
• Случајне шетње се користе за моделирање коцкања.
• У физици, случајне шетње су у основи метод процене Ферми.
• На вебу, сајт Твиттер користи случајне шетње да предложи кога да пратиши

Варијанте случајне шетње

Велики број врста стохастичких процеса су сматрани да су слични чистим случајним шетњама, али где је дозвољено да једноставна структура буде уопштена. Чиста структура може бити окарактерисана корацима који дефинишу независне и идентично расподељене случајне променљиве.

Случајна шетња на графиконима

Случајни хода дужине к бесконачно могућег графика Г са кореном 0 је стохастички процес са случајним променљивама$X_{1},X_{2},\dots ,X_{k}$ тако да$X_{1}=0$ и ${X_{i+1}}$ је највиша тачка изабрана равномерно насумично из суседа $X_{i}$.

Онда за број $p_{v,w,k}(G)$ је вероватноћа да се случајна шетња од дужине к почетком у в завршава у В. Конкретно, ако је Г графикон са кореном 0, $p_{0,0,2k}$онда је вероватноћа да $2k$-корак слободне шетње враћа на 0.

Претпоставимо сада да наш град више није савршен квадрат мреже. Када наш пијаница достигне одређену раскрсницу он бира између различитих путева са једнаком вероватноћом. Стога, ако чвор има седам излаза пијанац ће ићи на сваки од њих са вероватноћом једне седмине. Ово је случајна шетња на графикону. Хоће ли наш пијаница доћи до своје куће? Испоставило се да под веома благим условима, одговор је увек да. На пример, ако су дужине свих блокова између А и Б (где су а и б било која два коначно позитивна броја), онда ће пијанац, готово сигурно, доћи до своје куће. Обратите пажњу да не претпостављамо да је графикон равни, односно град може да садржи тунеле и мостове. Један од начина да се докаже овај резултат јесте коришћење везе са електричним мрежама. Узмите мапу града и поставите једно ома отпорник на сваком блоку. Сада мери "отпор између тачке и бесконачности". Другим речима, изаберите неки број Р и предузети све тачке у електричну мрежу са удаљености веће од Р из наше тачке и послати их заједно. Ово је сада коначно електрична мрежа и можемо мерити отпор од наше тачке до жичаних тачака. Узмите Р до бесконачности. Граница се зове отпор између тачке и бесконачности. Испоставило се да је следеће тачно (елементарни доказ може се наћи у књизи Доиле и Снелл):

Теорема: график је пролазан ако и само ако је отпор између тачке и бесконачности коначан. Није важно ако је тачка изабрана ако је повезан график.

Другим речима, у пролазном систему, један само треба да превазиђе коначан отпор да се стигне до бесконачности из било које тачке. У повратном систему, отпор од било које тачке у бесконачности је бесконачан.

Ова карактеризација рецидива и пролазности је веома корисна, а посебно нам омогућава да анализирамо случај града састављен у равни са ограниченом раздаљином.

Случајна шетња на графу је веома посебан случај Марковог ланца. За разлику од општег Марковог ланца, случајна шетња на графикону има имовину која се зове време симетрија или понављање. Грубо говорећи, овај хотел, који се назива принцип детаљног баланса, значи да ће вероватноћа прећи дати пут у једном правцу или у другом и имамо веома једноставну везу између њих (ако је граф редовно, они су само једнаки). Ова некретнина има значајне последице.

Од 1980-их, много истраживања је извршено у циљу повезивања својства графикона до случајне шетње. Поред електричне мрежне конекције горе описане, постоје значајне везе са исопериметричним неједнакостима, функционалне неједнакости као што су Соболев и Поенкаре неједнакости и својства решења Лапласове једначине. Значајан део овог истраживања био је фокусиран на Цаилеием графовима коначно остварених група. На пример, доказ Даве Баиер и Перси Диацонис да 7 кундацима Схуффлес довољно да се меша шпил карата и на снази је резултат о случајној шетњи на групи СН, а доказ користи структуру групе у суштинском начину. У многим случајевима ови дискретни резултати преносе на, или су добијени од многострукости и група.

Добра референца за случајну шетњу на графиконима је онлине књига Алдоус и напуните. За групе види књигу Воесс.

Ако транзиција кернела$p(x,y)$је сама случајна (на основу животне \ омега) онда се случајна шетња зове "случајна шетња по случајном окружењу". Када закон случајне шетње укључује случајности \ омега, закон се зове аннеалед закон; С друге стране, ако \ омега се сматра фиксним, закон се назива гаси закон. Погледајте књигу Хугхес или предавање  Зеитоуни.

Можемо да размишљамо о избору сваке могуће предност са истом вероватноћом као максималном локалном несигурношћу (ентропија) . Ми такође можемо то урадити на глобалном нивоу - у максималној ентропији случајне шетње (МЕРВ) желимо да сви путеви буду подједнако вероватни, или другим речима: за свака два вертекес, сваки пут дате дужине је подједнако вероватан. Ова случајна шетња има много јаче особине локализације.

Полу-интерагујућа случајна шетња

Постоји велики број занимљивих модела случајних путања у којој сваки корак зависи од прошлости у компликованом начину. Сви су сложенији за аналитичко решавање од уобичајеног случајног корака; даље, понашање било ког модела случајне шетње је добити помоћу рачунара. Примери укључују:

• Полу-избегавајућа шетња (Мадрас и Сладе 1996)).

Полу-избегавајућа шетња дужине н о з ^ д је случајна п Н-корак који почиње у пореклу, чини прелазе само између суседних локација у з ^ д, никада не посећује сајт, и равномерно је изабран међу свим тим путевима. У две димензије, до услед само-хватање, типична само-избегавајућа шетња је врло кратка, док у вишу димензију расте изнад свих граница. Овај модел се често користи у физици полимера (од 1960)

• Избрисана петља случајне шетње (Gregory Lawler).
• Ојачана случајна шетња (Robin Pemantle 2007).
• Процес истраживања.
• Мултиагент случајне шетње.

Дуге колерацијске шетње

Дуге корелацијске временске серије се могу наћи у многим биолошким, климатских и економских системима..

• Heartbeat records
• Non-coding DNA sequences
• Volatility time series of stocks
• Temperature records around the globe

Види још

• Брауново кретање

Литература

• Stein, Rolf Alfred (1972). Tibetan Civilization. Stanford University Press. ISBN 978-0-8047-0901-9. 
• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, https://web.archive.org/web/20040921020230/http://stat-www.berkeley.edu/users/aldous/RWG/book.html
• Ben-Avraham D.; Havlin S., Diffusion and Reactions in Fractals and Disordered Systems Архивирано на сајту Wayback Machine (4. октобар 2011), Cambridge University Press, 2000.
• Doyle, Peter G.; Snell, J. Laurie (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22. Mathematical Association of America. arXiv:math.PR/0001057. ISBN 978-0-88385-024-4.  MR 920811
• Feller, William (1968). An Introduction to Probability Theory and its Applications. I. ISBN 978-0-471-25708-0. 
• Hughes, Barry D. (1996). Random Walks and Random Environments. Oxford University Press. ISBN 978-0-19-853789-2. 
• Mackenzie, Dana, "Taking the Measure of the Wildest Dance on Earth", Science, Vol. 290, 8 December 2000.
• Norris, James (1998). Markov Chains. Cambridge University Press. ISBN 978-0-521-63396-3. 
• Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1-2):149–160, March 1921.
• Révész, Pal (2013). Random Walk in Random and Non-random Environments (3rd изд.). World Scientific Pub Co. ISBN 978-981-4447-50-8. 
• Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.
• Toshikazu Sunada (2012), Topological Crystallography --With a View Towards Discrete Geometric Analysis--, Surveys and Tutorials in the Applied Mathematical Sciences, Vol. 6, Springer

Спољашње везе

• Pólya's Random Walk Constants
• Random walk in Java Applet
• Quantum random walk