Passeggiate casuali

Per contare esattamente il numero dei diversi percorsi di $n$ passi che conducono a una delle possibili posizioni finali procediamo un passo alla volta.

... eccetera.

Si noti che le posizioni raggiunte stanno su quadrati concentrici di equazioni $|x|+|y|=k$ dove $k=n \mod 2, n\mod 2 +2, n\mod 2 +4, \cdots, n.$

Il numero di percorsi per raggiungere dopo $n$ passi una certa posizione $(x,y)$ forma uno schema numerico che ricorsivamente può descriversi in javascript nel modo seguente:

Si riconosce una generalizzazione del triangolo di Tartaglia, quello ottenuto dalla somma reiterata delle liste $[0,...L]$ e $[...L,0]$ a partire da $L=[1]$, generalizzazione che può ottenersi analogamente a partire dalla matrice $M=[[1]]$ reiterando la somma di \[M=\begin{bmatrix} M & \begin{matrix}0 \\ \vdots\\ 0\end{matrix} \\ \begin{matrix}0\cdots 0\end{matrix} & 0 \end{bmatrix}+ \begin{bmatrix} \begin{matrix}0 \\ \vdots\\ 0\end{matrix} & M \\ 0 &\begin{matrix}0\cdots 0\end{matrix} \end{bmatrix}+ \begin{bmatrix} 0 & \begin{matrix}0\cdots 0\end{matrix} \\ \begin{matrix}0 \\ \vdots\\ 0\end{matrix} & M \end{bmatrix}+ \begin{bmatrix} \begin{matrix}0\cdots 0\end{matrix} &0 \\ M &\begin{matrix}0 \\ \vdots\\ 0\end{matrix} \end{bmatrix}\]

Come già visto in precedenza le probabilità si possono ottenere calcolando una media delle matrici anche anziché una somma.

Si osserva facilmente che i coefficienti al rigo $i$ e colonna $j$ sono $\binom{n}{i}\cdot \binom{n}{j}$.

Dunque il n° di percorsi di $n$ passi che conducono alla posizione $(x,y)$ è \[\begin{cases}\binom{n}{\frac{n+|x|+|y|}{2}}\cdot\binom{n}{\frac{n+|x|-|y|}{2}}&\mbox{quando}\;\;n+x+y\;\; \mbox{è pari e } |x|+|y|\le n\\ 0 &\mbox{altrimenti} \end{cases} \]( si osservi che con un numero dispari $n$ di passi sono raggiungibili solo posizioni con $y\pm x$ dispari, con un numero pari $n$ di passi sono raggiungibili solo posizioni con $y\pm x$ pari).

Il risultato ottenuto precedentemente o con i binomiali è dunque quello che si può ottenere sommando il numero dei percorsi che conducono nelle posizioni vicine.

Questo schema numerico è detto piramide di Pascal a base quadrata.
Si tratta anche dei coefficienti $c_n(X,Y)$ dello sviluppo $$\displaystyle (x+y+x^{-1}+y^{-1})^n=\sum_{X,Y}c_n(X,Y)x^Xy^Y$$ dove $(X,Y)$ è la posizione raggiunta.
Si possono determinare dallo sviluppo $$\displaystyle (x+y+x^{-1}+y^{-1})^n=\sum_{i_1+i_2+i_3+i_4=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4}x^{i_1}y^{i_2}x^{-i_3}y^{-i_4}=$$ $$\displaystyle =\sum_{i_1+i_2+i_3+i_4=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4}x^{i_1-i_3}y^{i_2-i_4}$$ dove $i_1$ sono i passi in direzione $x$ positivo, $i_3$ quelli in direzione $x$ negativo, $i_2$ i passi in direzione $y$ positivo e $i_4$ quelli in direzione $y$ negativo, per cui $$\begin{cases}i_1+i_2+i_3+i_4=n\\i_1-i_3= X\\i_2-i_4=Y \end{cases} \longrightarrow \begin{cases}i_2=\frac{n+X+Y}{2}-i_1\\ i_3= i_1-X\\ i_4=\frac{n+X-Y}{2}-i_1 \end{cases}$$ Si ottiene quindi $$\displaystyle (x+y+x^{-1}+y^{-1})^n==\sum_{X,Y}\sum_{i}\frac{n!}{i!\big(\frac{n+X+Y}{2}-i\big)!(i-X)!\big(\frac{n+X-Y}{2}-i\big)!}x^Xy^Y$$ da cui $$\displaystyle c_n(X,Y)=\binom{n}{\frac{n+X+Y}{2}}\sum_{i}\binom{\frac{n+X+Y}{2}}{i}\binom{\frac{n-(X+Y)}{2}}{i-X}$$ Dalla proprietà dei binomiali (identità di Vandermonde) $$\displaystyle \binom{m+n}{l}=\sum_{i=0}^l\binom{m}{i}\binom{n}{l-i},$$ o anche $$\displaystyle \binom{m+n}{n+l}=\sum_{i=l}^{n+l}\binom{m}{i}\binom{n}{i-l},$$ deriva appunto \[ c_n(X,Y)=\binom{n}{\frac{n+X+Y}{2}}\binom{n}{\frac{n+X-Y}{2}}\]

Si osservi che $|X|+|Y|=n-2k \longrightarrow c_n(X,Y)=\binom{n}{k}\binom{n}{|X|+k}=\binom{n}{k}\binom{n}{|Y|+k}$.

Possiamo visualizzare tali valori attribuendo loro uno dei $256^3-1$ colori $C=256^2R+256G+B$, dove $R,G,B$ sono le intensità, tra 0 e 255, dei colori rosso, verde, blu, da cui si ricava:

Possiamo esprimere $c_n(X,Y)$ come una sommatoria elegante considerando i modi possibili $n_x, n_y=n-n_x$ di distribuire gli $n$ passi lungo i due assi: $$c_n(X,Y) = \sum_{\substack{n_x+n_y=n \\ n_x \ge |X|, n_y \ge |Y|}} \binom{n}{n_x\;\;n_y} \binom{n_x}{\frac{n_x+X}{2}} \binom{n_y}{\frac{n_y+Y}{2}}$$ dove il termine $\binom{n}{n_x\;\;n_y}=\binom{n}{n_x}$ conta in quanti modi puoi decidere di fare $n_x$ passi totali lungo l'asse $x$ e quindi $n_y=n-n_x$ conta i passi lungo $y$. Una volta considerati $n_x$ passi lungo l'asse $x$, il termine $\binom{n_x}{\frac{n_x+X}{2}}$ calcola in quanti modi quei passi portano esattamente alla coordinata $X$ ciò che va moltiplicato quanti sono i modi che portano a $Y$ con i passi lugo l'altra direzione e si somma su tutte le possibili ripartizioni dei passi $n$.
Così \[c_n(X,Y) = \sum_{n_x=0}^n\frac{n!}{\frac{n+X+Y}{2}!\frac{n-X-Y}{2}!}\frac{\frac{n+X+Y}{2}!}{\frac{n_x+X}{2}!\frac{n-n_x+Y}{2}!}\frac{\frac{n-X-Y}{2}!}{\frac{n_x-X}{2}!\frac{n-n_x-Y}{2}!}=\] \[=\binom{n}{\frac{n+X+Y}{2}}\sum_{n_x=0}^n\binom{\frac{n+X+Y}{2}}{\frac{n_x+X}{2}}\binom{\frac{n-(X+Y)}{2}}{\frac{n_x-X}{2}}=\binom{n}{\frac{n+X+Y}{2}}\binom{n}{\frac{n+X-Y}{2}}.\]

Un calcolo più astuto dei precedenti consiste nel fattorizzare $(x+y+x^{-1}+y^{-1})$ come $(u+u^{-1})(v+v^{-1})$ che, poiché $ \left(u + \frac{1}{u}\right)\left(v + \frac{1}{v}\right) = uv + \frac{1}{uv} + \frac{u}{v} + \frac{v}{u}$, è possibile tramite il cambio di variabili $x = uv \quad \text{e} \quad y = u/v$.
Quindi $$(x+y+x^{-1}+y^{-1})^n = \left(u + u^{-1}\right)^n \left(v + v^{-1}\right)^n$$Ora dobbiamo solo convertire il termine target $x^X y^Y$ nelle nuove variabili $u$ e $v$:$$x^X y^Y = (uv)^X (u/v)^Y = u^{X+Y} v^{X-Y}$$Il problema si riduce quindi a trovare il coefficiente di $u^{X+Y}$ nell'espansione di $(u + u^{-1})^n$ e quello di $v^{X-Y}$ nell'espansione di $(v + v^{-1})^n$.
Per un'espressione della forma $(z + z^{-1})^n$, il termine generico dell'espansione binomiale è $\binom{n}{k} z^k (z^{-1})^{n-k} = \binom{n}{k} z^{2k-n}=\binom{n}{\frac{n+h}{2}}z^h$.
Ne ricaviamo che il coefficiente di $u^{X+Y}$ è $\binom{n}{\frac{n+X+Y}{2}}$ mentre quello di $v^{X-Y}$ è $\binom{n}{\frac{n+X-Y}{2}}$.
Moltiplicando i due risultati otteniamo la formula finale.