Passeggiate casuali
Posizioni raggiunte in passeggiate senza memoria, a passo costante, simmetriche.
Il primo aspetto da approfondire analiticamente della passeggiata casuale dell'ubriaco è quello delle posizioni raggiunte dopo $n$ passi, una variabile aleatoria che possiamo indicare con $X_n$:
| N° di passi | valori di $X_n$: posizioni raggiunte |
|---|---|
| 1 | –1, +1 |
| 2 | –2, 0 , +2 |
| 3 | –3, –1, +1, +3 |
| …. | |
| $n = 2k$ | $-n,-n+2,\dots,-4,-2,0,+2,+4,\dots,n-2,n$ |
| $n=2k+1$ | $-n,-n+2,\dots,-3,-1,+1,+3,\dots,n-2,n$ |
Ciascuna di queste posizioni può essere raggiunta seguendo percorsi diversi:
| N° di passi | N° di percorsi che conducono a ogni valore di $X_n$ |
|---|---|
| 1 | 1 , 1 |
| 2 | 1, 2 , 1 |
| 3 | 1, 3, 3, 1 |
| …. | |
| $n$ | $1, C_{n,1}, C_{n,2}, C_{n,3}, ..., C_{n,n-3}, C_{n,n-2}, C_{n,n-1}, 1 $ |
Il numero totale di percorsi effettuabili con $n$ passi, la somma dei componenti la riga $n$-esima del triangolo di Pascal-Tartaglia, è $2^n$.
Nel modo più naturale, cioè ricorsivamente, questo schema, si può descrivere in javascript nel modo seguente:
function nPercorsi(n,x) {
if ( n == 0 ) return 1
else if( n < Math.abs(x) ) return 0
else if( (n+Math.abs(x))%2 > 0 ) return 0
else if( n == Math.abs(x) ) return 1
else return nPercorsi(n-1,x-1) + nPercorsi(n-1,x+1)
}
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
Si può ottenere anche iterando:
L = [...L,0].map((x, i) => x + [0,...L][i])
che data la lista $L$, inizialmente $L=[1]$, corrispondente a una riga dello schema, forma la lista corrispondente alla riga successiva sommando la lista $[0,...L]$, nella quale si antepone a $L$ l'elemento 0, con la lista $[...L,0]$, nella quale $L$ viene prolungata con uno zero finale.
Quindi
L = [1];
for (var k=0; k<n; k++)
L = [...L,0].map((x, i) => x + [0,...L][i])
crea le prime $n+1$ righe.
Volendo inserire nello schema anche il numero, nullo, di percorsi per raggiungere posizioni pari per un numero dispari di passi o viceversa:
L = [1];
for(var i=0; i<n;i++){
L = [...L,0,0].map((x,k)=>x+[0,0,...L][k]);
}
1
1,0,1
1,0,2,0,1
1,0,3,0,3,0,1
1,0,4,0,6,0,4,0,1
Lo schema del triangolo numerico di Pascal-Tartaglia si può ottenere anche per diagonali iterando:
diag.map((sum => value => sum += value)(0))
che produce somme cumulate a partire dalla diagonale formata di tutti 1.
diag = new Array(n+1).fill(1)
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | |
| 1 | 3 | 5 | ||
| 1 | 4 | |||
| 1 |
Il termine generico $C_{n,k}$, che si scrive anche $\binom{n}{k}$, si può ottenere calcolando $\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}$. Con Javascript si può quindi ottenere anche nel modo seguente, arrotondando eventualmente il risultato:
C = 1;
for (var i=1; i=k; i++) C*=(n-k+i)/i;
oppure in una sola riga:
new Array(k).fill().reduce((num,e,i)=>num*=(n-k+1+i)/(i+1),1)
Così ad esempio $C\big($$\big)=$10
Particolarmente interessante è osservare che nello sviluppo di \[\displaystyle(x^{-1}+x)^n=\sum_{k=0}^n\binom{n}{k}x^{-n+k}x^{k}= \sum_{k=0}^n\binom{n}{k}x^{2k-n}=\sum_{\overset{n+X \text{ pari}}{X=-n}}^n\binom{n}{\frac{n+X}{2}}x^{X}\] gli esponenti di $x$ sono le posizioni raggiunte dopo gli $n$ passi mentre i coefficienti esprimono il numero di passeggiate diverse che conducono alla stessa posizione.
Se $n$ è il numero di passi, la posizione raggiunta è $X=2k-n,\quad \mbox{con}\;\; k\in\{0,1,2,...,n\}$ e il numero di percorsi possibili per raggiungerla è $\binom{n}{\frac{n+X}{2}}=\binom{n}{\frac{n-X}{2}}$.
Se poi indichiamo con $n_+$ il numero dei passi nel verso positivo e $n_-$ quello dei passi nel verso opposto, allora $\begin{cases}n_++n_-=n\\ n_+-n_-=X \end{cases}$ da cui $\begin{cases}n_+=\frac{n+X}{2}\\ n_-=\frac{n-X}{2} \end{cases}.$
In conclusione, la posizione raggiunta dopo $n$ passi è una variabile casuale $X_n$ che assume i valori \[-n, -n+1, \cdots, -1, 0, 1, \cdots, n-1, n\] e la cui distribuzione di probabilità, cioè la probabilità di raggiungere la posizione $x$ dopo $n$ passi, si può ottenere dividendo il numero di modi di raggiungere quella posizion per il numero totale $2^n$ di percorsi effettuabili. \[p(X_n=x)=\begin{cases}\binom{n}{\frac{n+x}{2}}\frac{1}{2^n} &\quad\mbox{se n+x è pari}\\ 0 &\quad\mbox{altrimenti}\end{cases}\]
Si può ottenere la distribuzione delle probabilità con una minima variazione del procedimento per determinare le righe del triangolo di Pascal-Tartaglia.
L = [1];
for (var k=0; k<n; k++)
L = [...L,0].map((x, i) => (x + [0,...L][i])/2)
o anche
È più chiaro, poiché sintetico, rappresentare graficamente la legge di distribuzione della variabile $X_n$ mediante istogramma.