Passeggiata aleatoria

In matematica, una passeggiata aleatoria (random walk) è la formalizzazione dell'idea di prendere passi successivi in direzioni casuali. Matematicamente parlando, è il processo stocastico più semplice, il processo markoviano, la cui rappresentazione matematica più nota è costituita dal processo di Wiener.

Esempio di otto passeggiate aleatorie in una dimensione partendo da 0. Il grafico mostra la posizione sulla linea (asse verticale) al variare del tempo (numero di passi effettuati - asse orizzontale).

Un'animazione raffigurante un esempio di tre passeggiate aleatorie, simili ad un moto browniano, su un toro, a partire dal centro dell'immagine.

Il termine fu introdotto per la prima volta da Karl Pearson nel 1905.

Caso monodimensionale

In una passeggiata aleatoria monodimensionale si studia il moto di una particella puntiforme vincolata a muoversi lungo una retta nelle due direzioni consentite. Ad ogni movimento essa si sposta (a caso) di un passo a destra (con una probabilità fissata $p$) o a sinistra con una probabilità $1-p$, ed ogni passo è di lunghezza uguale e indipendente dagli altri. Ci proponiamo di calcolare con quale probabilità dopo N movimenti la particella tornerà (ammesso che torni!) nel punto di partenza. Introduciamo la seguente variabile aleatoria $X(N)$ che fornisce il numero di passi a sinistra compiuti dopo $N$ movimenti; essa in particolare modella il numero di teste uscite dopo $N$ lanci di una moneta opportunamente truccata. Ovviamente questa è una variabile aleatoria discreta con distribuzione binomiale. Notiamo inoltre che l'evento "tornare nell'origine" equivale a compiere su $2N$ passi totali esattamente $N$ passi a sinistra; quindi la probabilità cercata equivale a $P\{X=N\},$ con $X$ binomiale di parametri $n=2N,k=N,p$ quindi

$P\{X=N\}={\frac {(2N)!}{N!(2N-N)!}}p^{N}(1-p)^{N}={2N \choose N}(p-p^{2})^{N}.$

Ad esempio, se ho pari possibilità che la particella vada a destra o a sinistra ad ogni passo ($p=1/2$), la probabilità di ritorno all'origine dopo $2N$ passi sarà di

$P\{X=N\}={2N \choose N}\left({\frac {1}{2}}\right)^{2N}\approx {\frac {1}{\sqrt {N\pi }}},$

dove abbiamo applicato l'approssimazione di Stirling per $N$ sufficientemente grande,

$N!\sim {\sqrt {2\pi N}}\;\left({\frac {N}{e}}\right)^{N}$ .

Ora ricordando che il valore atteso di una variabile aleatoria è dato da

$E[X]=\sum _{n=0}^{\infty }nP(n),$

e che ciò equivale in questo caso a cercare la media dei "successi" precedenti ad un "fallimento" dei ritorni in infiniti passi (ossia sfruttiamo la distribuzione geometrica associata), otteniamo che il numero medio di ritorni all'origine della particella, detta $p$ la probabilità di un singolo ritorno, è dato dalla serie geometrica

$\mu =\sum _{n=0}^{\infty }np^{n}(1-p)\approx \sum _{n=0}^{\infty }{\frac {1}{\sqrt {n\pi }}}\rightarrow +\infty ,$

da cui, utilizzando la relazione $\mu ={\frac {1}{1-p}}-1$, desumiamo che la probabilità della particella di tornare prima o poi all'origine è tendente a $1$. Questo significa che nonostante la frequenza dei ritorni si abbassi con l'aumentare del numero di passi compiuti, essi ci saranno comunque sempre in un numero infinito di passi compiuti.

Quindi possiamo concludere che una particella con uguali probabilità di movimento a destra e sinistra lasciata libera di camminare casualmente all'infinito con grande probabilità torna infinite volte al punto da cui è partita.

Caso bidimensionale

In una passeggiata aleatoria bidimensionale si studia il moto di una particella vincolata a muoversi sul piano spostandosi casualmente ad ogni passo a destra o a sinistra con probabilità $1/2$, verso l'alto o verso il basso con probabilità $p=1/2$. In pratica ad ogni passo può compiere un movimento lungo una delle quattro diagonali con probabilità $1/4$. Ci si chiede con che probabilità la particella tornerà al punto di partenza. Questo caso può essere studiato come la composizione di due camminate aleatorie monodimensionali; anche qui una particella è nell'origine dopo $2N$ passi solo se ne ha compiuti esattamente $N$ a sinistra e $N$ in alto (conseguentemente altrettanti a destra e in basso). Dette allora $X(n)=\{n{\text{ passi a sinistra su }}N{\text{ passi}}\}$ e c$Y(n)=\{n{\text{ passi in alto su }}N{\text{ passi}}\}$ due variabili binomiali come nel paragrafo precedente avremo:

$P\left\{X=N,Y=N\right\}=P\left\{X=N\right\}P\left\{Y=N\right\},$

dato che le variabili casuali $X$ e $Y$ sono stocasticamente indipendenti. Quindi riprendendo i calcoli del paragrafo precedente otterremo:

$P\{X=N,Y=N\}=\left({2N \choose N}\left({\frac {1}{2}}\right)^{2N}\right)^{2},$

e, detta come prima $p$ la probabilità di un singolo ritorno al punto di partenza, ottengo che il numero medio di ritorni quando $N$ tende all'infinito è:

$\mu =\sum _{n=0}^{\infty }np^{n}(1-p)\approx \sum _{n=0}^{\infty }{\frac {1}{n\pi }}\rightarrow +\infty ,$

da cui, utilizzando la relazione $\mu ={\frac {1}{1-p}}-1$, desumiamo che la probabilità della particella di tornare prima o poi all'origine è tendente a $1$. Quindi anche nel caso bidimensionale una particella libera di camminare casualmente con uguale probabilità nelle quattro direzioni tornerà infinite volte al punto di partenza.

Caso tridimensionale

In una passeggiata aleatoria tridimensionale si studia il moto di una particella vincolata a muoversi nello spazio spostandosi casualmente ad ogni passo a destra o a sinistra con probabilità $1/2$, verso l'alto o verso il basso con probabilità $p=1/2$, avanti o indietro con probabilità $1/2$. In pratica ad ogni passo può compiere un movimento lungo una delle otto diagonali con probabilità $1/8$. Ci si chiede con che probabilità la particella tornerà al punto di partenza. È chiaro che posso studiare analogamente al caso bidimensionale questo caso considerandolo come una composizione di tre passeggiate aleatorie monodimensionali indipendenti. Come nel paragrafo precedente, dopo aver introdotto la variabile aleatoria $Z$ che ritorna il numero di passi "in su" ottengo:

$P\{X=N,Y=N,Z=N\}=\left({2N \choose N}\left({\frac {1}{2}}\right)^{2N}\right)^{3},$

approssimabile con Stirling a ${\frac {1}{(n\pi )^{\frac {3}{2}}}}.$

Questa volta, contrariamente ai casi delle $1$ e $2$ dimensioni, abbiamo

$\mu =\sum _{n=0}^{\infty }{\frac {1}{(n\pi )^{\frac {3}{2}}}}\approx 0,315$

da cui, utilizzando la relazione $\mu ={\frac {1}{1-p}}-1$, desumiamo che la probabilità della particella di tornare prima o poi all'origine è di circa $p=0,239$.

Bibliografia

• Paolo Baldi, Calcolo delle probabilità e statistica, 2ª ed., McGraw-Hill, 1998, ISBN 9788838607370.
• E. Parzen (1999): Stochastic Processes, Holden-Day
• M. P. Rogantin (2004): Introduzione alla statistica, C.L.U.T., Torino

Voci correlate

• Moto browniano
• Processo markoviano
• Proprietà di Markov

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su passeggiata aleatoria

Collegamenti esterni

• (EN) random walk, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Passeggiata aleatoria, su MathWorld, Wolfram Research.
• Passeggiata aleatoria semplice, su fp.freeshell.org. URL consultato il 1º maggio 2006 (archiviato dall'url originale il 21 febbraio 2007).