Passeggiate casuali
Senza memoria, a passo costante in due direzioni ortogonali, simmetriche: analisi.
Si può determinare il numero dei percorsi per raggiungere la posizione $(X,Y,Z)$ come coefficienti dello sviluppo di \[\displaystyle (x+y+x^{-1}+y^{-1}+z+z^{-1})^n=\sum_{|X|+|Y|+|Z|\le n}c_n(X,Y,Z)\cdot x^Xy^Yz^Z.\]
Ad esempio con il software C.A.S. Maxima il comando expand((x+y+x^(-1)+y^(-1)+z+z^(-1))^2) produce:
\[\small {{z}^{2}}+2 y z+\frac{2 z}{y}+2 x z+\frac{2 z}{x}+\frac{2 y}{z}+\frac{2}{y z}+\frac{2 x}{z}+\frac{2}{x z}+\frac{1}{{{z}^{2}}}+{{y}^{2}}+2 x y+\frac{2 y}{x}+\frac{2 x}{y}+\frac{2}{x y}+\frac{1}{{{y}^{2}}}+{{x}^{2}}+\frac{1}{{{x}^{2}}}+6\]
in cui si può leggere che il numero di percorsi per tornare a $(0,0,0)$ dopo due passi è 6 oppure con
coeff(expand((x+y+x^(-1)+y^(-1)+z+z^(-1))^4),z,0)
\[{{y}^{4}}+4 x\, {{y}^{3}}+\frac{4 {{y}^{3}}}{x}+6 {{x}^{2}}\, {{y}^{2}}+\frac{6 {{y}^{2}}}{{{x}^{2}}}+28 {{y}^{2}}+4 {{x}^{3}} y+48 x y+\frac{48 y}{x}+\frac{4 y}{{{x}^{3}}}+\frac{4 {{x}^{3}}}{y}+\frac{48 x}{y}+\frac{48}{x y}+\frac{4}{{{x}^{3}} y}+\]\[+\frac{6 {{x}^{2}}}{{{y}^{2}}}+\frac{6}{{{x}^{2}}\, {{y}^{2}}}+\frac{28}{{{y}^{2}}}+\frac{4 x}{{{y}^{3}}}+\frac{4}{x\, {{y}^{3}}}+\frac{1}{{{y}^{4}}}+{{x}^{4}}+28 {{x}^{2}}+\frac{28}{{{x}^{2}}}+\frac{1}{{{x}^{4}}}+90\]
mostra i numeri di percorsi per raggiungere le posizioni $(X,Y,0)$.
Poiché $$\displaystyle (x+y+x^{-1}+y^{-1}+z+z^{-1})^n=\sum_{i_1+i_2+i_3+i_4+i_5+i_6=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4\;\; i_5\;\; i_6}x^{i_1}y^{i_2}x^{-i_3}y^{-i_4}z^{i_5}z^{-i_6}=$$
$$\displaystyle =\sum_{i_1+i_2+i_3+i_4+i_4+i_5+i_6=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4\;\; i_5\;\; i_6}x^{i_1-i_3}y^{i_2-i_4}z^{i_5-i_6}$$
e da $$\begin{cases}i_3+i_4+i_5+i_6&=n-i_1-i_2\\i_3&= i_1-X\\i_4&=i_2-Y \\i_5-i_6&=Z\end{cases}$$
ricaviamo
$$\displaystyle (x+y+x^{-1}+y^{-1}+z+z^{-1})^n=\sum_{X,Y,Z}\sum_{i_1,i_2}\frac{n!}{i_1!i_2!(i_1-X)!(i_2-Y)!\big(\frac{n+X+Y+Z}{2}-i_1-i_2\big)!\big(\frac{n+X+Y-Z}{2}-i_1-i_2\big)!}x^Xy^Yz^Z$$
Così
$$\displaystyle c_n(X,Y,Z)=\binom{n}{\frac{n+X+Y+Z}{2}}\sum_{i_1,i_2}\binom{\frac{n+X+Y+Z}{2}}{i_1\;\;i_2\;\;\frac{n+X+Y+Z}{2}-i_1-i_2}\binom{\frac{n-X-Y-Z}{2}}{i_1-X\;\;i_2-Y\;\;\frac{n+X+Y-Z}{2}-i_1-i_2}=$$
$$\displaystyle=\binom{n}{\frac{n+X+Y+Z}{2}}\sum_{i_1}\left(\binom{\frac{n+X+Y+Z}{2}}{i_1}\binom{\frac{n-X-Y-Z}{2}}{i_1-X}\sum_{i_2}\binom{\frac{n+X+Y+Z}{2}-i_1}{i_2}\binom{\frac{n+X-Y-Z}{2}-i_1}{i_2-Y}\right)= $$
sempre in conseguenza dell'identità di Vandermonde,
$$\displaystyle=\binom{n}{\frac{n+X+Y+Z}{2}}\sum_{i_1}\binom{\frac{n+X+Y+Z}{2}}{i_1}\binom{\frac{n-X-Y-Z}{2}}{i_1-X}\binom{n+X-2i_1}{\frac{n+X+Y-Z}{2}-i_1}=$$
$$\displaystyle=\binom{n}{\frac{n+X+Y+Z}{2}}\sum_{i}\binom{\frac{n+X+Y+Z}{2}}{i}\binom{\frac{n-X-Y-Z}{2}}{i-X}\binom{n+X-2i}{\frac{n+X-2i}{2}+\frac{Y-Z}{2}}= ...?$$
Consideriamo anche che $c_n(X,Y,Z)$ non cambia per permutazioni di $X,Y,Z$ e inoltre $c_n(X,Y,Z)=c_n(\pm X,\pm Y,\pm Z)$, ne deriva che $c_n(X,Y,Z)=c_n(|X|,|Y|,|Z|)$. Poiché $|X|+|Y|+|Z|$ è la minima lunghezza di un percorso per raggiungere $(X,Y,Z)$, il fattore $\binom{n}{\frac{n+|X|+|Y|+|Z|}{2}}$ rappresenta la parte del calcolo che è comune a tutti i percorsi: l'obbligo di effettuare esattamente $\frac{n+|X|+|Y|+|Z|}{2}$ passi nella direzione "giusta" per superare la distanza minima, indipendentemente da come questi passi sono distribuiti tra gli assi $X, Y$ e $Z$. Invece $n-(|X|+|Y|+|Z|)$ sono i passi in eccesso la cui metà $\frac{n+(|X|+|Y|+|Z|)}{2}$ è il numero di coppie di cicli. Il fattore $\frac{n+|X|+|Y|+|Z|}{2}$ rappresenta quindi una componente "di traslazione" mentre l'altro fattore rappresenta una componente "di ciclo".
Purtroppo non sembra esistere una formula "chiusa" semplice come nel caso bidimensionale, un'eccezione fortunata dovuta a una fattorizzazione algebrica speciale. Tuttavia, possiamo esprimere $c_n(X,Y,Z)$ come una sommatoria elegante considerando i modi possibili $n_x, n_y, n_z$ di distribuire gli $n$ passi lungo i tre assi (x, y, z):$$c_n(X,Y,Z) = \sum_{\substack{n_x+n_y+n_z=n \\ n_x \ge |X|, n_y \ge |Y|, n_z \ge |Z|}} \binom{n}{n_x\;\;n_y\;\;n_z} \binom{n_x}{\frac{n_x+X}{2}} \binom{n_y}{\frac{n_y+Y}{2}} \binom{n_z}{\frac{n_z+Z}{2}}$$dove il termine $\binom{n}{n_x\;\;n_y\;\;n_z}$ conta in quanti modi si possono fare $n_x$ passi totali lungo l'asse $x$, $n_y$ passi lungo $y$ e $n_z$ passi lungo $z$. Considerati poi $n_x$ passi lungo l'asse $x$, il termine $\binom{n_x}{\frac{n_x+X}{2}}$ calcola in quanti modi quei passi possono portare esattamente alla coordinata $X$ ciò che va moltiplicato per ogni asse e infine sommato su tutte le possibili ripartizioni dei passi $n$.
Il "trucco" applicato nel caso bidimensionale che consiste nel fattorizzare $(x+x^{-1}+y+y^{-1}) = (u+u^{-1})(v+v^{-1})$ per poi trasformare una somma in un prodotto, permettendo di calcolare i coefficienti indipendentemente e moltiplicarli alla fine, nel caso tridimensionale non funziona considerando che $x+x^{-1}+y+y^{-1}+z+z^{-1}$ ha sei termini mentre $(u+u^{-1})(v+v^{-1})(w+w^{-1})$ ne ha otto.
Si osservi che \[|X|+|Y|+|Z|=n \longrightarrow c_n(X,Y,Z)=\binom{n}{|X|\;\;|Y|\;\;|Z|}\]
ciò relativamente alle posizioni raggiungibili distribuite sulle facce di una doppia piramide a base quadrata con vertici in $(\pm n,0,0)$, $(0,\pm n, 0)$ e $(0,0,\pm n)$.
Si osservi anche \[|X|+|Y|+|Z|=n-2k \longrightarrow c_n(X,Y,Z)=\binom{n}{k}\cdot d_{n,k}(|X|,|Y|,|Z|)\]
dove \[d_{n,k}(|X|,|Y|,|Z|)=\sum_{i=0}^{n-k}\binom{n-k}{i}\binom{k}{i-|X|}\binom{n+|X|-2i}{|X|+|Y|+k-i}\]
e si esamini lo schema numerico triangolare formato dai $d_{n,k}(|X|,|Y|,|Z|)$.
Ad esempio per $n= $ si ottiene, al variare di $k$, la seguente lista di schemi triangolari:
|
|
Si osservi che come $c_n(X,Y,Z)$ non varia permutando i suoi argomenti, così accade per $d_n(|X|,|Y|,|Z|)$ e ciò giustifica le simmetrie degli schemi triangolari.
Se consideriamo solo le posizioni di coordinate $X,Y,Z$ non negative raggiunte con $n$ passi si ha che: \[M_n[k][r][c] = d_{n,k}(r-c,c,n-2k-r)\] dove $ 0\le r,c\le n-2k$, ovvero \[d_{n,k}(X,Y,Z)= M_n\left[\frac{n-X-Y-Z}{2}\right]\left[X+Y\right]\left[Y\right]\] e \[M_n[k][r][c]=\sum_{i=0}^{n-k}\binom{n-k}{i}\binom{k}{i+c-r}\binom{n+r-c-2i}{r+k-i}\] \[ =\sum_{i=0}^{n-k}\binom{n-k}{i}\binom{k}{i-c}\binom{n+c-2i}{r+k-i}\] dove in particolare \[M_n[0][r][c] =\binom{n}{r}\binom{r}{c}=\binom{n}{r-c\;\;c\;\;n-r}\]
Si osservi che:
- per $n>1$ si ha
$d_{n,1}(n-2,0,0)= d_{n,1}(0,n-2,0)= d_{n,1}(0,0,n-2)=2(n-1)+1$, i numeri dispari; - per $n>3$ si ha
$\displaystyle d_{n,2}(0,0,n-4)=3(n-2)^2+(n-2)+1$ che fornisce $(1,5,)15,31,53,81,115,155,201,253,311,375,445,521,603,691,785,885,991, ...$ (A056108);
$\displaystyle d_{n,1}(0,1,n-3)=\frac{3}{2}(n-2)^2+\frac{5}{2}(n-2)+1$ che fornisce $(1,5,)12,22,35,51,70,92,117,145,176, ...$; - per $n>5$ si ha $\displaystyle d_{n,3}(0,0,n-6)=\frac{10}{3}(n-3)^{3}-(n-3)^{2}+\frac{11}{3}(n-3)+1$ ottenendo $(1,7,31,)93,213,411,707,1121,1673,2383,3271,4357,5661,7203,9003,11081,13457,16151, ...$;
$\displaystyle d_{n,2}(0,1,n-5)=\frac{5 }{3}{(n-3)^{3}}+3{(n-3)^{2}}+\frac{7}{3}(n-3)+1$ ottenendo $(1,8,31,)80,165,296,483,736,1065,1480,1991, ...$;
$\displaystyle d_{n,1}(0,2,n-4)=\frac{2}{3}(n-3)^3+\frac{5}{2}(n-3)^2+\frac{17}{6}(n-3)+1$ che fornisce $(1,7,22,)50,95,161,252,372,525,715,946, ...$; - per $n>7$ si ha $\displaystyle d_{n,4}(0,0,n-8)=\frac{35}{12} {(n-4)^{4}}-\frac{25 }{6}{(n-4)^{3}}+\frac{121}{12} {(n-4)^{2}}-\frac{5}{6}(n-4)+1$ ottenendo $(1,9,53,213,)639,1551,3239,6063,10453,16909,26001,38369, ...$;
$\displaystyle d_{n,3}(0,1,n-7)=\frac{35 }{24}{(n-4)^{4}}+\frac{25 }{12}{(n-4)^{3}}+\frac{73 }{24}{(n-4)^{2}}+\frac{41}{12}(n-4)+1$ ottenendo $(1,11,60,213,)570,1266,2471,4390,7263,11365,17006,24531,34320,46788, ...$;
$\displaystyle d_{n,2}(0,2,n-6)=\frac{5}{8}(n-4)^4+\frac{31}{12}(n-4)^3+\frac{31}{8}(n-4)^2+\frac{35}{12}(n-4)+1$ ottenendo $(1,11,53,165,)400,826,1526,2598,4155,6325,9251,13091,18018,24220, ...$;
$\displaystyle d_{n,1}(0,3,n-5)=\frac{5}{24}(n-4)^4+\frac{17}{12}(n-4)^3+\frac{79}{24}(n-4)^2+\frac{37}{12}(n-4)+1$ che fornisce $(1,9,35,95,)210,406,714,1170,1815,2695,3861, ...$
Si osservi anche $d_{n,1}(0,c,n-2-c)=d_{n-1,1}(0,c-1,n-2-c)+d_{n-1,1}(0,c,n-3-c)+\binom{n}{c}$ ovvero che $M_{n}[1][c][c]=M_{n-1}[1][c-1][c-1]+M_{n-1}[1][c][c]+\binom{n}{c}$.
Inoltre, come già osservato in precedenza \[c_{n}(X,Y,Z)=c_{n-1}(X+1,Y,Z)+c_{n-1}(X-1,Y,Z)+c_{n-1}(X,Y+1,Z)+\]\[+c_{n-1}(X,Y-1,Z)+c_{n-1}(X,Y,Z+1)+c_{n-1}(X,Y,Z-1)\] e quindi \[d_{n,k}(X,Y,Z)=\frac{k}{n}\left(d_{n-1,k-1}(X+1,Y,Z)+d_{n-1,k-1}(X,Y+1,Z)+d_{n-1,k-1}(X,Y,Z+1)\right)+\]\[+\frac{n-k}{n}\left(d_{n-1,k}(X-1,Y,Z)+d_{n-1,k}(X,Y-1,Z)+d_{n-1,k}(X,Y,Z-1)\right)\]
In particolare il numero dei percorsi diversi che riportano al punto di partenza - come del resto che ritornano in un punto qualsiasi - dopo $2n$ passi è \[\begin{align} \sum_{r+s+t=n}\binom{2n}{r\;\;r\;\;s\;\;s\;\;t\;\;t} &=\sum_{r+s+t=n}\binom {\color{magenta}{2n}}{\underbrace{r\;\;s\;\;t}_{\color{magenta}n}\;\;\underbrace{r\;\;s\;\;t}_{\color{magenta}n}}=\\ &=\sum_{r+s+t=n}\left[\color{magenta}{\binom {2n}n}\binom{n}{r\;\;s\;\;t}^2\right]=\\ &=\binom {2n}n\sum_{r=0}^n\binom nr ^2 \;\sum_{s=0}^{n-r}\binom {n-r}s ^2=\\ &=\binom {2n}n\sum_{r=0}^n \binom nr ^2\binom {2(n-r)}{n-r}=\\ &=\color{green}{\binom {2n}n\sum_{r=0}^n \binom nr ^2\binom {2r}r\qquad\blacksquare}\end{align}\]
Ovviamente la probabilità di raggiungere la posizione $(x,y,z)$ in $n\ge |x|+|y|+|z|$ passi è $\frac{c_n(x,y,z)}{6^n}$.
George Polya dimostrò nel 1921 che è inferiore a 1 la probabilità che in una passeggiata casuale in un reticolo tridimensionale, pur camminando per sempre, si torni all'inizio, come pure che si raggiunga qualsiasi altro punto assegnato. Nel 1940 W. H. McCrea e F. J. W. Whipple dimostrarono che la probabilità di tornare al punto di partenza dopo aver vagato non importa quanto su un reticolo cubico infinito è di circa 0.35 (Pólya's Random Walk Constants).