Passeggiate casuali

Iniziamo col condurre alcune semplici riflessioni.

Per esempio se $L=1$, dopo n passi le posizioni raggiunte costituiscono una variabile aleatoria $X_{1,n}$:

Ciascuna di queste posizioni può essere raggiunta con percorsi diversi:

Tali coefficienti $\binom{n}{k}_2,\;\;k=0,1,\dots,2n$, per cui $\displaystyle (1+x+x^2)^n=\sum_{k=0}^{2n}\binom{n}{k}_2x^k$ ovvero $\displaystyle (x^{-1}+1+x)^n=\sum_{X=-n}^n\binom{n}{n+X}_2x^X$, sono detti trinomiali e soddisfano la relazione \[\displaystyle\binom {n}{k+2}_2=\binom {n-1}{k}_2+\binom {n-1}{k+1}_2+\binom {n-1}{k+2}_2.\] Si noti che $\binom {n}{k}_2=\binom {n}{2n-k}_2$.
Si tratta anche del numero di modi distinti in cui $k$ oggetti indistinguibili possono essere distribuiti in $n$ urne distinguibili consentendo al massimo 2 oggetti in ciascuna urna.

I trinomiali sono riducibili a binomiali: \[\displaystyle\binom {n}{k}_2=\sum_{j=\lfloor\frac{k+1}{2}\rfloor}^k\binom{n}{j}\binom{j}{k-j}.\] Equivalentemente \[\displaystyle\binom {n}{k}_2=\sum_{j=\lfloor\frac{k}{2}\rfloor}^k\binom{n}{k-j\;\;\;2j-k\;\;\;n-j}.\] Infatti considerando che $$\displaystyle(a + b + c)^n=\sum_{i_1+i_2+i_3=n}\binom{n}{i_1\;\;i_2\;\;i_3}a^{i_1}b^{i_2}c^{i_3}$$ e quindi $$\displaystyle(1 + x + x^2)^n=\sum_{i_1+i_2+i_3=n}\binom{n}{i_1\;\;i_2\;\;i_3}x^{i_2+2i_3}$$ da cui, posto $\begin{cases}i_2+2i_3=k \\ i_2+i_3=n-i_1 \end{cases}$, si ricava $$\displaystyle(1 + x + x^2)^n=\sum_{k=0}^{2n}\Big(\sum_{i_1}\frac{n!}{i_1!\;\;(2n-2i_1-k)!\;\;(i_1+k-n)!}\Big)x^k$$ ovvero, ponendo poi $j=n-i_1$, \[\displaystyle\binom {n}{k}_2=\sum_{j}\binom{n}{n-j\;\;\;\;\;2j-k\;\;\;\;\;k-j}=\sum_{j}\binom{n}{j}\binom{j}{k-j}.\] Se consideriamo $\displaystyle(x^{-1}+1 + x)^n=\sum_{i_1+i_2+i_3=n}\binom{n}{i_1\;\;i_2\;\;i_3}x^{-i_1+i_3}$, posto $\begin{cases}-i_1+i_3=X \\ i_1+i_3=n-i_2 \end{cases}$, si ricava \[(x^{-1}+1 + x)^n=\sum_{X=-n}^{n}\left(\sum_{i_2}\frac{n!}{\left(\frac{n-X-i_2}{2}\right)!\;\;i_2!\;\;\left(\frac{n+X-i_2}{2}\right)!}\right)x^X=\sum_{X=-n}^{n}\left(\sum_{j}\binom{n}{\frac{j-X}{2}\;\;n-j\;\;\;\frac{j+X}{2}}\right)x^X\] \[=\sum_{X=-n}^{n}\left(\sum_{j}\binom{n}{j}\binom{j}{\frac{X+j}{2}}\right)x^X\] da cui\[\displaystyle\binom {n}{n+X}_2=\sum_{j}\binom{n}{j}\binom{j}{\frac{X+j}{2}}\] Alternativamente $$\displaystyle(x^{-1}+1 + x)^n=\sum_{j=0}^n\binom{n}{j}(x^{-1}+x)^j=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^j\binom{j}{i}x^{j-2i}=$$ \[=\sum_{j=0}^n\binom{n}{j}\sum_{k=-j}^j\binom{j}{\frac{k+j}{2}}x^{k}=\sum_{k=-n}^n\sum_{j=|k|}^n\binom{n}{j}\binom{j}{\frac{k+j}{2}}x^{k}.\] Del resto \[(x^{-1}+1 + x)^n=(1 + x + x^2)^nx^{-n}= \sum_{k=0}^{2n}\sum_{j}\binom{n}{j}\binom{j}{k-j}x^{k-n}= \sum_{h=-n}^{n}\sum_{j}\binom{n}{j}\binom{j}{n+h-j}x^{h}.\]

La somma dei $2n+1$ elementi di ciascuna riga è una potenza del 3 e ciascuna riga dello schema può ottenersi dalla precedente con javascript nel modo seguente:

ovvero per produrre tutto lo schema:

Si tratta della distribuzione teorica.

Se per esempio se $L=2$, dopo n passi le posizioni raggiunte costituiscono una variabile aleatoria $X_{2,n}$:

Ciascuna di queste posizioni può essere raggiunta secondo percorsi diversi:

La somma dei $4n+1$ elementi di ciscuna riga è $5^n$.

Ogni riga si ottiene con javascript mediante l'iterazione:

Si tratta della distribuzione teorica, che all'aumentare di $n$ assume una forma sempre più "a campana".

Se poi si vuole attribuire diversa probabilità $p=[p0,p1,p2,p3,p4]$ alla lunghezza e verso di ogni singolo passo occorrerà modificare:

In generale i coefficienti dello sviluppo di $\displaystyle (1+x+x^2+\cdots+x^{s})^n=\sum_{k=0}^{s\cdot n}\binom {n}{k}_{s}x^k$ si chiamano binomiali generalizzati di ordine $s$.

Alcune loro proprietà sono:

• $\displaystyle\begin{cases}\binom {1}{0}_s=\dots=\binom {1}{s}_s=1 \\ \binom {n}{k}_s=0 &\quad n\lt 0,\; k\gt ns\\ \binom {n}{k}_s=\sum_{j=0}^{s}\binom{n-1}{k-j}_s &\quad 0\le k \le sn\end{cases}$
• $\displaystyle\binom{n}{k}_s=\binom{n}{sn-k}_s$
• $\displaystyle\sum_{k=0}^{sn}\binom{n}{k}_s=(s+1)^n$
• $\displaystyle\sum_{k=0}^{sn}(-1)^k\binom{n}{k}_s=\begin{cases}1 &\quad\;\; s=2t \\ 0 &\quad\;\; s=2t+1\end{cases}$
• $\displaystyle\binom {n}{k}_{s+1}=\sum_{j=0}^k\binom{n}{j}\binom{j}{k-j}_s$
• $\displaystyle\binom {n}{1+s}_{s}=\sum_{i=0}^{s-1}\binom{n+i}{2+i}$
• $\displaystyle\binom {n}{k}_s=\sum_{j=0}^{\left \lfloor \frac{k}{s} \right \rfloor}(-1)^j\binom{n}{j}\binom{n+k-(s+1)j-1}{n-1}$
• $\displaystyle\binom {n}{k}_s=\sum_{\begin{matrix} i_0+i_1+\dots+i_s=n \\ i_1+2i_2+\dots+si_s=k \end{matrix}}\binom{n}{i_0\;\;i_1\;\;i_2\;\;\cdots\;\;i_{s}}=$
  $\displaystyle=\sum_{k_i\le k_{i+1}}\binom{n}{k_1\;\;k_2-k_1\;\;k_3-k_2\;\;\cdots\;\;n-k_{s}}$

I coefficienti dello sviluppo di $(1+x+x^2+x^3+x^4+...+x^{2L-1})^n$ si ottengono modificando la sola istruzione
qL = Math.pow(2,L)
in
qL = Math.pow(2,L)-1

Se consideriamo lo sviluppo di $$\displaystyle (x^{-L}+x^{-L+1}+\cdots+x^0+\cdots+x^{L-1}+x^L)^n=x^{-nL}(1+x+x^2+\cdots+x^{2L})^n=$$ $$=\sum_{k=0}^{2L\cdot n}\binom {n}{k}_{2L+1}x^{k-nL},$$ gli esponenti $k-nL$ di $x$ sono le posizioni raggiunte al termine della passeggiata.

Se poi, seguendo una legge binomiale, attribuiamo la probabilità $\frac{1}{4^L}\left( 2L \atop k\right)$ di compiere un passo di ampiezza, con segno, $k-2L$ - che poi è la velocità - allora dopo $n$ passi posizioni raggiunte e probabiltà relative si ottengono dallo sviluppo di \[\displaystyle \frac{1}{4^{nL}}\left(\left( 2L \atop 0\right)x^{-L}+\left( 2L \atop 1\right)x^{-L+1}+\cdots+\left( 2L \atop L\right)x^0+\cdots+\left( 2L \atop {2L-1} \right)x^{L-1}+\left( 2L \atop 2L\right)x^L\right)^n=\] \[=\frac{x^{-nL}}{4^{nL}}(1+x)^{2nL}= \sum_{k=0}^{2nL}\frac{1}{4^{nL}}\binom {2nL}{k}x^{k-nL}\] e quindi in questo caso la posizione raggiunta infine è una variabile aleatoria che segue ancora una legge binomiale.