Il grillo salterino.

[3m0o]

Consideriamo \( [0,n] \cap \mathbb{N} \) con \(n \in \mathbb{N} \). Supponiamo che vi sia un grillo che saltella allegramente lungo gli interi di questo segmento.
Quando il grillo è posizionato sul numero \(k\), con \( 0 < k < n \), egli ad ogni step salta a destra oppure a sinistra di un numero con probabilità \(1/2\) indipendentemente dal passato, i.e. con probabilità \( 1/2 \) salta sul numero \(k+1\) e con probabilità \(1/2\) sul numero \(k-1\). Quando il grillo raggiunge lo \(0\) oppure il numero \(n\) si ferma. Sia \(H(k)\) la probabilità che il grillo raggiunge \(n\) prima di raggiungere lo \(0\) partendo da \(k\). Chiaramente \(H(0)=0\) e \(H(n)=1\).

Quanto vale \(H(k)\) ?

[axpgn]

Testo nascosto, fai click qui per vederlo

$k/n$ ?

Cordialmente, Alex

[3m0o]

Si ma come lo dimostri?

[axpgn]

Con calma

Testo nascosto, fai click qui per vederlo

$H(0)=0$
$H(1)=1/2H(0)+1/2H(2)=1/2H(2)$
$H(2)=1/2H(1)+1/2H(3)=1/4H(2)+1/2H(3)=2/3H(3)$
....
$H(n-1)=(n-1)/nH(n)=(n-1)/n$

poi

$H(n-2)=(n-2)/(n-1)*(n-1)/n=(n-2)/n$

ecc.

[dan95]

Mi ricorda molto la passeggiata aleatoria

[Mathita]

Davvero un bel problemino questo qui! Non so per quale motivo, mi è venuta in mente la Macchina di Turing probabilistica (che in qualche modo è intimamente legata alla random walk). Bellino.

[ghira]

Quando il grillo è posizionato sul numero \(k\), con \( 0 < k < n \), egli ad ogni step salta a destra oppure a sinistra di un numero con probabilità \(1/2\) indipendentemente dal passato, i.e. con probabilità \( 1/2 \) salta sul numero \(k+1\) e con probabilità \(1/2\) sul numero \(k-1\). Quando il grillo raggiunge lo \(0\) oppure il numero \(n\) si ferma. Sia \(H(k)\) la probabilità che il grillo raggiunge \(n\) prima di raggiungere lo \(0\) partendo da \(k\). Chiaramente \(H(0)=0\) e \(H(n)=1\).

Quanto vale \(H(k)\) ?

Testo nascosto, fai click qui per vederlo

$k/n$ in quanto la posizione media è sempre $k$ quindi lo è anche alla fine della partita e per avere una media ponderata di $k$ usando solo i valori $0$ e $n$ il peso di $n$ deve essere $k/n$.

[3m0o]

Posto la mia soluzione

Testo nascosto, fai click qui per vederlo

Abbiamo chiaramente che per ogni \( 1 \leq k \leq n-1\) risulta che \(H(k) = \frac{1}{2} \left( H(k-1) + H(k+1) \right) \). Abbiamo un sistema ad \(n-1\) equazioni con \(n-1\) incognite, i.e. i valori di \(H(k) \) per \(k = \{ 1 ,\ldots, n-1\} \). Si nota abbastanza facilmente che \(H(k) = \frac{k}{n} \) è una soluzione. Supponiamo che esistono due soluzioni differenti, \( H_1, H_2 \), denotiamo \(D=H_1-H_2\). Chiaramente, abbiamo che \( D(0)=D(n) =0 \). Ma poiché le soluzioni sono distinte allora esiste \(0 < k < n \) tale che \( D(k) \neq 0 \) in particolare esiste un massimo o un minimo, wlog un massimo. Sia dunque \(k_M \) tale che \(D(k_M) = M \) è il massimo. Siccome \( M \) è il massimo abbiamo che \( D(k_M-1) \leq M \) e \( D(k_M+1) \leq M \), ma abbiamo anche
\[ D(k_M) = M = \frac{1}{2} \left( D(k_M-1) + D(k_M+1) \right) \]
dunque
\[ D(k_M)= D(k_M-1) = D(k_M+1) \]
da cui deduciamo che
\[ D(k) = 0 \]
per ogni \( 0 \leq k \leq n \). Assurdo. Dunque \( H_1=H_2\) e \( H(k)= \frac{k}{n} \).