Una camminata casuale: 1 – passi e probabilità

Un pedone è posto in $x=0$. Si lancia una moneta e, se esce testa il pedone si sposta di una unità verso destra, altrimenti si sposta di una unità verso sinistra. Qual è il numero medio di lanci da effettuare affinché il pedone raggiunga una distanza $n$ dall’origine? Chiamo $E(x)$ ($x\in \mathbb N$) il numero medio di lanci affinché il pedone passi dalla posizione $0$ a una posizione distante $x$ dall’origine, e $E(a;b)$ ($a,b\in \mathbb N$) il numero medio di lanci affinché il pedone passi da una posizione distante $a$ dall’origine a una posizione distante $b$ dall’origine.

Un’osservazione che risulterà necessaria più avanti è che se $a\leq b$, poiché per giungere a una posizione distante $b$ dall’origine il pedone dovrà prima necessariamente passare da una posizione distante $a<b$ dall’origine, deve essere $E(b)=E(a)+E(a;b)$, ovvero $E(a;b)=E(b)-E(a)$.

Chiaramente $E(0)=0$ e $E(1)=1$.

Quando il pedone giunge in posizione distante $1$ dall’origine c’è una probabilità di $\frac12$ che col lancio successivo arrivi alla posizione distante $2$ dall’origine e $\frac12$ di probabilità che torni alla posizione $x=0$. Si ha pertanto $E(2)=1+\frac12\cdot1+\frac12[1+E(2)]$ da cui ricavo $E(2)=4$. Questo suggerisce che in generale sia $E(n)=n^2$.

Procedo per induzione e suppongo che sia $E(k) =k^2$ per $k=0, 1,\ldots, n-1$.

Sia $n>2$: prima di arrivare ad una posizione distante $n$ dall’origine il pedone dovrà passare per una posizione distante $n-1$ dall’origine. Una volta giunto in posizione a distanza $n-1$ dall’origine c’è una probabilità di $\frac12$ che col lancio successivo giunga in posizione distante $n$ dall’origine ed una probabilità di $\frac12$ che vada in una posizione distante $n-2$ dall’origine.

Allora si ha:$$E(n)=E(n-1)+\frac12\cdot1+\frac12[1+E(n-2;n)]=\\= E(n-1) + \frac12 + \frac12 [1+E(n)-E(n-2)]=\\=E(n-1)+\frac12+\frac12+\frac12\cdot E(n)-\frac12\cdot E(n-2)\ ,$$ovvero$$E(n)=2E(n-1)+2-E(n-2)\ .$$

Tenendo presente l’ipotesi induttiva si ha:$$E(n)=2E(n-1)+2-E(n-2)=2(n-1)^2+2-(n-2)^2=\\=(2n^2-4n+2)+2+(-n^2+4n-4)=n^2\ .\ \square$$Questo risultato così “pulito” c’è solo per il moto browniano “binario” unidimensionale anche se, approssimativamente, vale anche per quello in più dimensioni.

Per la cronaca, la varianza (vedi sequenza OEIS A072819) è data da $\sigma^2=\frac23n^2(n^2-1)$ (questo non so dimostrarvelo, se volete nella pagina OEIS c’è il link ad un articolo complicatissimo).

Possiamo generalizzare il problema in diversi modi. Ad esempio, supponiamo che i due limiti non siano posti simmetricamente rispetto alla posizione iniziale ma siano in $x=-k$ e $x=+n$ ($k$ e $n$ naturali positivi): qual è il numero medio di passi prima che il pedone raggiunga uno dei due limiti?

Adoperiamo un altro approccio e supponiamo di avere il pedone in posizione $x\geq0$ e di voler conoscere il numero medio di passi prima di raggiungere o la posizione corrispondente a $0$ o quella corrispondente a $N$ ($N$ naturale, $N\geq x$). Chiamiamo $L(x)$ il numero medio di lanci prima di raggiungere uno dei due limiti. Si avrà $L(0)=L(N)=0$. Inoltre, poiché dopo un passo il pedone sarà con probabilità $\frac12$ in posizione $x-1$ e con probabilità $\frac12$ in posizione $x+1$ si avrà $$L(x)=\frac12[1+L(x-1)]+\frac12[1+L(x+1)]$$che possiamo riscrivere come $$[L(x+1)-L(x)]-[L(x)-L(x-1)]=D(x+1)-D(x)=-2$$dove ho posto $D(x)=L(x)-L(x-1)$. Una soluzione per $D$ è data da $D(x)=-2x+k$ e quindi per $L$ una soluzione è data da $L(x)=-x^2+bx+c$ e, imponendo le condizioni $L(0)=0$ e $L(N)=0$, otteniamo$$L(x)=-x^2+Nx=x(N-x)\ .$$Che questa soluzione sia unica, almeno per la restrizione di $L$ in $[0,N]\cap\mathbb N$, possiamo vederlo riscrivendo le condizioni viste come un sistema di $n+1$ equazioni in $n+1$ incognite (utilizzo la notazione $L_x$ invece di $L(x)$ per alleggerire la scrittura):$$\left\{ \begin{array}{l} L_0=0 \\ L_0-2L_1+L_2=-2 \\ L_1-2L_2+L_3=-2 \\ \vdots\\ L_{N-3}-2L_{N-2}+L_{N-1}=-2 \\ L_{N-2}-2L_{N-1} + L_N=-2 \\ L_N=0 \end{array}\right.$$ovvero, in forma matriciale,$$\mathbf M\cdot \mathbf L= \left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & \cdots & 0\\ 1 & -2 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & -2 & 1 & 0 & \cdots& 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & 1 & -2 & 1 & 0\\ 0 & \cdots & \cdots & 0 & 1 & -2 & 1 \\ 0 & \cdots & \cdots & 0 & 0 & 0 & 1 \end{array}\right ) \left(\begin{array}{c}L_0\\L_1\\ L_2 \\ \vdots\\ L_{N-2}\\L_{N-1} \\L_N \end{array} \right )=\left( \begin{array}{c} 0 \\ -2 \\ -2\\ \vdots \\ -2 \\ -2 \\ 0 \end{array} \right) =\mathbf v\ ,$$e poiché $\mathbf M$ è non singolare (ne lasciamo la dimostrazione come esercizio al lettore 😉), la soluzione è unica.

Facendo una traslazione, avere il pedone in $x=0$ e i limiti in $-k$ e $+n$ è come avere il pedone in $x=k$ e i limiti in $0$ e $n+k$, e pertanto il numero medio di lanci o passi prima di raggiungere uno dei due limiti è $L_{n,k} = n\cdot k$. Risulta che in questo caso la varianza è $\sigma^2=\frac13nk(n^2+k^2-2)$ (vedi pagina OEIS A069971).

Torniamo ora con il pedone in posizione $x\geq0$ e vogliamo conoscere il numero medio di passi prima di raggiungere o la posizione corrispondente a $0$ o quella corrispondente a $N$ ($N$ naturale, $N\geq x$), ma stavolta le probabilità di muoversi verso sinistra e verso destra non sono uguali ma sono, rispettivamente, $p$ e $q=1-p$: qual è il numero medio di lanci prima di raggiungere uno dei limiti? Stavolta l’equazione per $L$ è$$L(x)=p\,[1 + L(x-1)] + q\, [1 + L(x+1) ]$$sempre con le condizioni $L(0)=0$ e $L(N)=0$.

Stavolta l’equazione funzionale non è risolvibile semplicemente come nel caso $p=q=\frac12$ e ho pertanto fatto ricorso a Stefano Tungsteno. Riarrangiando la soluzione in modo da evidenziare la invarianza rispetto alla permutazione $(p,x) \leftrightarrow (q,N-x)$ ottengo$$L(x)=\frac{x\,p^N+(N-x)q^N-Np^xq^{N-x}}{(p-q)(p^N-q^N)}\ .$$L’espressione perde di significato se $p=q$ ma, come è facile intuire, per $p$ che tende a $\frac12$ la funzione $L(x)$ tende a $x(N-x)$, infatti ponendo $p=\frac12+\varepsilon$ e $q=\frac12-\varepsilon$ risulta $L(x)=x(N-x)+O(\varepsilon)$.

Riportando il pedone in $x=0$ e i limiti in $-k$ e $+n$, il numero medio di passi prima di raggiungere uno dei due limiti è $$L_{n,k}=\dfrac{k\,p^{n+k}+n\,q^{n+k}-(n+k)p^kq^n}{(p-q)(p^{n+k}-q^{n+k})}\ .$$Ora possiamo chiederci: partendo da una posizione $x$, quali sono le probabilità che venga raggiunto il limite “inferiore” oppure quello “superiore”?

Consideriamo il caso del pedone in posizione $x$, con limiti in $0$ e $N$ ed equiprobabilità di muoversi verso sinistra o verso destra. Chiamo $P(x)$ la probabilità che il primo limite ad essere raggiunto sia quello in $0$. Si avrà $$P(x)=\frac12 P(x-1)+\frac12 P(x+1)\Leftrightarrow P(x+1)-P(x)=P(x)-P(x-1)$$e quindi la funzione $P(x)$ non può che essere lineare (almeno nella sua restrizione su $\mathbb N$) e, considerando che $P(0)=1$ e $P(N)=0$, otteniamo $P(x)=\dfrac{N-x}N$. La probabilità $Q(x)$ che il primo limite ad essere raggiunto sia quello in $N$ sarà quindi $Q(x)=1-P(x)=\dfrac xN$.

Posizionandoci inizialmente in $x=0$ con i limiti in $-k$ e $+n$, indicando con $P_{n,k}$ e $Q_{n,k}$ le probabilità che il percorso termini rispettivamente in $-k$ e $+n$, si avrà $$P_{n,k}=\dfrac n{n+k}\ ,\quad Q_{n,k} =\dfrac k{n+k}\ .$$

Se le probabilità di spostarsi verso sinistra o verso destra sono genericamente $p\neq\frac12$ e $q=1-p$ l’equazione per $P$ è $$P(x)=p\,P(x-1)+q\,P(x+1)\Leftrightarrow q[P(x+1)-P(x)]=p[P(x)-P(x-1)]\ .$$Ponendo $D(x)=P(x)-P(x-1)$ si ha $$q\,D(x+1)=p\,D(x) \Leftrightarrow D(x+1)=\frac pq D(x) \Leftrightarrow \\ \Leftrightarrow D(x)=\frac pq D(x-1)=\ldots=\left(\frac pq\right)^{x-1}D(1)\ .$$Ora si ha $$P(1)=P(0)+D(1)\\P(2)=P(0)+D(1)+D(2)\\\vdots\\ 0 = P(N) = P(0) + D(1) + \ldots + D(N) = 1 + D(1) \sum_{m=0}^{N-1} \left(\frac pq\right)^m=\\=1 + D(1) \, \frac{1-\left(\dfrac pq\right)^N}{1-\dfrac pq}\Leftrightarrow D(1)=-\frac{1-\dfrac pq}{1-\left(\dfrac pq\right)^N}$$avendo supposto $p\neq q$. Si avrà quindi$$\require{cancel}P(x)=P(0)+D(1)+\ldots + D(x)=1+D(1)\sum_{m=0}^{x-1} \left(\frac pq\right)^m=\\=1-\frac{\cancel{1-\dfrac pq}}{1-\left(\dfrac pq\right)^N}\frac{1-\left(\dfrac pq\right)^x}{\cancel{1-\dfrac pq}}\Rightarrow P(x)=\frac{\left(\dfrac pq\right)^x-\left(\dfrac pq\right)^N}{1-\left(\dfrac pq\right)^N}\ ,$$ e quindi $$Q(x)=1-P(x)=\frac{1-\left(\dfrac pq\right)^x}{1-\left(\dfrac pq\right)^N}=\frac{\left(\dfrac qp\right)^{N-x}-\left(\dfrac qp\right)^N}{1-\left(\dfrac qp\right)^N}$$dove l’ultima espressione evidenzia l’invarianza rispetto alla permutazione $(p,P,x) \leftrightarrow (q,Q,N-x)$.

Posizionandoci inizialmente in $x=0$ con i limiti in $-k$ e $+n$ si avrà $$P_{n,k}=\frac{\left(\dfrac pq\right)^k-\left(\dfrac pq\right)^{n+k}}{1-\left(\dfrac pq\right)^{n+k}}\ ,\quad Q_{n,k}=\frac{\left(\dfrac qp\right)^n-\left(\dfrac qp\right)^{n+k}}{1-\left(\dfrac qp\right)^{n+k}}\ .$$

Infine: sapendo che il pedone, partendo da una certa posizione ha terminato il percorso in un particolare limite, qual è il numero medio di passi che avrà compiuto? “Sperimentalmente” e per tentativi ho trovato quanto segue. Sono formule non dimostrate rigorosamente ma che hanno un certo supporto logico ed hanno mostrato di “funzionare” sempre perfettamente quando confrontate con i risultati di test Monte Carlo.

Chiamo $L_0(x)$ e $L_N(x)$ il numero medio di passi per le traiettorie che terminano rispettivamente in $0$ e $N$.

Per $p=q=\frac12$, limiti in $0$ e $N$ e posizione iniziale $x$ si ha$$L_0(x)=\frac13 x(2N-x),\quad L_N(x)=\frac13(N-x)(N+x)\\ \textrm{e si ha, come dev’essere, }L_0\cdot P(x) + L_N(x)\cdot Q(x)=L(x)\ .$$Per $p=q=\frac12$, limiti in $-k$ e $+n$ e posizione iniziale $0$, chiamando $L_{-k}$ e $L_{+n}$ il numero medio di passi per le traiettorie che terminano rispettivamente in $-k$ e $+n$, si ha quindi $$L_{-k}=\frac13 k(2n+k),\quad L_{+n}=\frac13n(2k+n)\\ \textrm{e si ha }L_{-k}\cdot P_{n,k} + L_{+n}\cdot Q_{n,k} =L_{n,k}\ .$$Per $p\neq q$, limiti in $0$ e $N$ e posizione iniziale $x$ si ha$$L_0(x)=\frac1{p-q}\left[ {N \frac{p^N+q^N}{p^N-q^N} - (N-x)\frac{p^{N-x}+q^{N-x}}{p^{N-x}-q^{N-x}}}\right ],\\ L_N(x) = \frac1{q-p}\left[ {N\frac{q^N+p^N}{q^N-p^N}-x\frac{q^x+p^x}{q^x-p^x}}\right ]\\[15pt] \textrm{e si ha }L_0(x)\cdot P(x) + L_N(x)\cdot Q(x)=L(x)\ .$$Per $p\neq q$, limiti in $-k$ e $+n$ e posizione iniziale $0$ si ha quindi $$L_{-k}=\frac1{p-q}\left[ {(n+k)\frac{p^{n+k}+q^{n+k}}{p^{n+k}-q^{n+k}}-n\,\frac{p^n+q^n}{p^n-q^n}}\right ]\ ,\\ L_{+n} = \frac1{q-p} \left[ { (n+k)\frac{q^{n+k}+p^{n+k}}{q^{n+k}-p^{n+k}}-k\,\frac{q^k+p^k}{q^k-p^k}}\right ]\\[15pt] \textrm{e si ha }L_{-k}\cdot P_{n,k} + L_{+n}\cdot Q_{n,k} =L_{n,k}\ .$$

La domanda che possiamo porci ora è: dopo $l$ passi qual è la probabilità che il pedone abbia raggiunto uno dei due limiti? o viceversa: affinché la probabilità di aver raggiunto uno dei due limiti sia $p$ quanti passi occorrono? Occorre studiare la funzione di distribuzione delle probabilità.

Stay tuned…

つづく

Figura 1. Andamento del numero medio di lanci $L(x)$ in funzione di $p$ per $N=8$.

Figura 2. Andamento della probabilità $P(x)$ in funzione di $p$ per $N=8$.

Figura 3. Andamento del numero medio di lanci $L_0(x)$ per le traiettorie terminate in posizione $0$ in funzione di $p$ per $N=8$. Non ho tracciato i grafici di $L_0(x)$ per $p>\frac12$ perché $L_0(x)$ non cambia se sostituiamo $p$ con $1-p$, ovvero è invariante per lo scambio $p \leftrightarrow q$, quindi il grafico per $p=0{,}6$ è lo stesso che si ha per $p=0{,}4$, eccetera.