Passeggiate casuali

Analizziamo altri aspetti di una passeggiata casuale con uguale probabilità di seguire un verso o quello opposto.

La distanza finale dalla posizione iniziale al termine di una passeggiata di n passi è una variabile casuale $d_n$ i cui valori $x=0,1,2,\dots,n$ e la cui distribuzione di probabilità $2\binom{n}{\frac{n+x}{2}}\frac{1}{2^n}$ sono visualizzabile nel seguente istogramma.

La media o valore atteso di questa distanza è $$\displaystyle \overline{d_n}=\sum_{x=-n}^n|x|p(X_n=x)=2\sum_\underset{n+x\;\; pari}{x=0}^nx\binom{n}{\frac{n+x}{2}}\frac{1}{2^{n}}=\frac{1}{2^{n-1}}\sum_{k=\lfloor\frac{n+1}{2}\rfloor}^n(2k-n)\binom{n}{k}=\frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}(n-2k)\binom{n}{k}.$$ Si hanno così le distanze medie finali 1, 2/2=1, 6/4=1.5, 12/8=1.5, 30/16=1.875, 60/32=1.875, 140/64=2.1875, 280/128=2.1875, 630/256=2.4609375, 1260/512=2.4609375.
Si può anche scrivere

Si ha anche: $$\displaystyle \overline{d_n}=\frac{n}{2^{n-1}}\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$$ (The On-Line Encyclopedia of Integer Sequences (OEIS))
nonché \[\overline{d_n}=\begin{cases}\frac{(n-1)!!}{(n-2)!!}& n\text{ pari} \\ \frac{(n)!!}{(n-1)!!}& n\text{ dispari}\end{cases}\] avendo posto $n!! = \begin{cases} 0!!=(-1)!!=1 \\ n(n-2)(n-4)\dots 2 & n\text{ pari}\\ n(n-2)(n-4)\dots 1 & n\text{ dispari}\end{cases}$
Inoltre per $n$ grande: \[\overline{d_n}\approx \sqrt{\frac{2n}{\pi}}\] Per il calcolo si può vedere "Random Walk--1-Dimensional" di Eric W. Weisstein, su MathWorld.

Il grafico seguente mostra in blu le distanze medie in funzione del numero di passi ed in grigio tale approssimazione.

Altre interessanti variabili casuali legate al moto dell'ubriaco sono:

• numero di passi per raggiungere per la prima volta una certa posizione,

• posizione massima raggiunta nel corso di un cammino di $n$ passi.

Per l'analisi teorica di queste due variabili è opportuno considerare prima l'evento

$E_{n,a,x}=$'dopo n passi viene raggiunta la posizione $x$ passando per la posizione $a$ almeno una volta'.

Evidentemente se $x\gt a$ l'evento è certo quindi ci occuperemo solamente dei casi in cui $x\le a$.
Possiamo osservare che considerando il grafico della legge oraria della passeggiata e riflettendone intorno alla retta $x=a$ la parte che precede il raggiungimento di $a$ per la prima volta, otteniamo un grafico della legge oraria del moto che partendo da $2a$ raggiunge $x$ e che dovrà passare necessariamente almeno una volta per $a$.

Dunque $E_{n,a,x}$ ha la stessa probabilità di raggiungere la posizione $2a-x$, o anche $x-2a$, in $n$ passi partendo da $0$: \[ p(E_{n,a,x})= \binom{n}{\frac{n+2a-x}{2}}\frac{1}{2^n}=\binom{n}{\frac{n+x-2a}{2}}\frac{1}{2^n}\]

Si consideri dunque ora la variabile aleatoria 'numero di passi per raggiungere per la prima volta la posizione $a$ in una passeggiata di $N$ passi'.
Affinché $n$ sia uno di questi numeri - i valori della variabile in questone - occorrerà, prima di compiere l'ultimo passo che da $a-1$ porti in $a$, che si sia verificato l'evento 'raggiunta la posizione $a-1$ in $n-1$ passi senza essere precedentemente passati per $a$'.
Quest'ultimo evento è il complementare di $E_{n-1,a,a-1}$ rispetto all'evento 'raggiunta la posizione $a-1$ in $n-1$ passi ', la cui probabilità è $$\binom{n-1}{\frac{n-1+(a-1)}{2}}\frac{1}{2^{n-1}}-\binom{n-1}{\frac{n-1+(2a-(a-1))}{2}}\frac{1}{2^{n-1}}.$$ La probabilità di raggiungere per la prima volta la posizione $a$ con $n$ passi è dunque \[\left(\binom{n-1}{\frac{n-1+(a-1)}{2}}-\binom{n-1}{\frac{n-1+(2a-(a-1))}{2}}\right)\frac{1}{2^{n-1}}\cdot \frac{1}{2}=\\=\left(\binom{n-1}{\frac{n-1+a-1}{2}}-\binom{n-1}{\frac{n-1+a+1}{2}}\right)\frac{1}{2^{n}}\]

considerando che quando $a$ è pari o dispari anche $n$ dovrà esserlo.
Si osservi che il numero di percorsi per raggiungere per la prima volta la posizione $a$ dopo $n$ passi risulta essere dunque la differenza tra il numero di percorsi per raggiungere la posizione $a-1$ dopo $n-1$ passi e il numero di percorsi per raggiungere la posizione $a+1$ dopo $n-1$ passi.
Si osservi anche che dev'essere $\displaystyle \sum_{n=1}^\infty\left(\binom{n-1}{\frac{n-1+a-1}{2}}-\binom{n-1}{\frac{n-1+a+1}{2}}\right)\frac{1}{2^{n}}=1$, quindi risulta certo che prima o poi si giungerà una prima volta alla posizione $a$, qualunque essa sia.

Possiamo confrontare la distribuzione teorica con quella sperimentale simulando passeggiate di passi.

Si osservi che la posizione può anche non essere mai raggiunta con quel numero di passi e che la probabilità di un tale evento è quanto manca per raggiungere l'unità alla somma delle probabilità visualizzate. Nei dati sperimentali è riportata la frequenza relativa dell'evento ' è raggiunta per la prima volta la posizione $a$ dopo un numero di passi $\ge n$ '.

La probabilità che ' $a$ è la posizione massima raggiunta in $n$ passi ' è quella di passare per $a$ almeno una volta in $n$ passi senza essere mai passati per $a+1$, cioè dell'evento che si esprime come $\displaystyle\bigcup_{x\le a}\left(E_{n,a,x} - E_{n,a+1,x}\right)$.
La sua probabilità è $$\displaystyle\sum_{x\le a}\left(\binom{n}{\frac{n+2a-x}{2}}-\binom{n}{\frac{n+2a+2-x}{2}}\right)\frac{1}{2^n}$$ ovvero in particolare la somma \[\binom{n}{\frac{n+a}{2}}-\binom{n}{\frac{n+a+2}{2}}+\\ +\binom{n}{\frac{n+a+1}{2}}-\binom{n}{\frac{n+a+3}{2}}+\\ +\binom{n}{\frac{n+a+2}{2}}-\binom{n}{\frac{n+a+4}{2}}+\\ + \cdots +\\ +\binom{n}{\frac{n+n-2}{2}}-\binom{n}{\frac{n+n}{2}}\] nella quale si elidono molti termini uguali così che resta la probabilità \[\left(\binom{n}{\frac{n+a}{2}}+\binom{n}{\frac{n+a+1}{2}}\right)\frac{1}{2^n}\]

dove uno dei due termini è zero.

Possiamo confrontare la distribuzione teorica con quella sperimentale simulando passeggiate composte da 10 passi:

Interessante è considerare anche l'ultimo passaggio per la posizione iniziale nel corso di una passeggiata che ovviamente potrà avvenire solo dopo un numero pari $2k$ di passi con $k=0,1, \cdots, n$ per cui consideremo $2n$ il numero di passi della intera passeggiata.

Indichiamo $E_{2n,2k}$ l'evento "nella passeggiata di $2n$ passi, l'ultimo passaggio per la posizione iniziale si è avuto dopo $2k$ passi". Equivale a "è stata raggiunta la posizione iniziale dopo $2k$ passi" e "non viene mai raggiunta la posizione iniziale dopo i $2n-2k$ passi restanti". A sua volta quest'ultimo evento equivale a "raggiungere +1 al primo passo" e poi "non scendere più al di sotto di questa posizione nei $2n-2k-1$ passi restanti" oppure "raggiungere -1 al primo passo" e poi "non salire più al di sopra di questa posizione nei $2n-2k-1$ passi restanti". I due eventi alternativi sono evidentemente equiprobabili. Inoltre "non salire più al di sopra di questa posizione nei $2n-2k-1$ passi restanti" equivale a "sia quella iniziale la posizione massima raggiunta in $2n-2k-1$ passi".

In conclusione $$\displaystyle\binom{2k}{k}\frac{1}{2^{2k}}\cdot\left(\binom{2n-2k-1}{\frac{2n-2k-1}{2}}+\binom{2n-2k-1}{\frac{2n-2k-1+1}{2}}\right)\frac{1}{2^{2n-2k-1}}$$ ovvero $$\displaystyle\binom{2k}{k}\frac{1}{2^{2k}}\cdot\binom{2n-2k-1}{n-k}\frac{1}{2^{2n-2k-1}}$$ dove $$\displaystyle\binom{2n-2k-1}{n-k}=\\=\binom{2n-2k}{n-k}\frac{n-k}{2n-2k}=\binom{2n-2k}{n-k}\frac{1}{2}$$ e quindi \[p(E_{2n,2k})=\binom{2k}{k}\binom{2n-2k}{n-k}\frac{1}{2^{2n}}\]

Per $n$ grandi, mediante la formula di Stirling, si ottiene \[p(E_{2n,2k})\approx \frac{1}{\pi\sqrt{k(n-k)}}.\] Da qui si ottiene anche la probabilità che l'ultimo passaggio per la posizione iniziale nel corso di una passeggiata di $2n$ passi sia inferiore a $2k$ è \[p\approx\int_{0}^{\frac{k}{n}}\frac{dx}{\pi\sqrt{x(1-x)}}=\frac{2}{\pi}\arcsin\sqrt\frac{k}{n}\] avendo preventivamente posto $x=\frac{k}{n}$.