SNS 2015 - 2

[Drago96]

Una stanza ha 4 pareti laterali, il soffitto e il pavimento. Una mosca si trova inizialmente sul soffitto, e comincia a muoversi seguendo queste regole:

• se lascia il pavimento o il soffitto, con probabilità $1/5$ torna sulla superficie che ha lasciato, oppure finisce su una delle pareti laterali con probabilità $1/5$ per ciascuna di esse
• se lascia una delle pareti laterali, può andare su ciascuna delle altre 3 pareti, sul soffitto e sul pavimento con probabilità $1/5$ per ciascuna delle supefici

Qual è la probabilità che la mosca si trovi sul pavimento dopo $k$ mosse?

[matpro98]

Tutte le probabilità sono uguali, è davvero così semplice??

[Drago96]

Asintoticamente sì, ma le formule esatte sono ovviamente diverse, già solo per il fatto che la probabilità al "passo 0" di essere sul soffitto è 1, e quella delle altre pareti è 0...

[cip999]

Testo nascosto:

Sia $S_k$ la probabilità che la mosca atterri sul pavimento dopo $k$ mosse partendo dal soffitto. Si definiscano analogamente $P_k$ (partenza dal pavimento) e $L_k$ (partenza da una parete laterale qualsiasi). Allora valgono le relazioni:
$$\begin{cases} S_k = \frac{1}{5}S_{k - 1} + \frac{4}{5}L_{k - 1} \\ P_k = \frac{1}{5}P_{k - 1} + \frac{4}{5}L_{k - 1} \\ L_k = \frac{1}{5}S_{k - 1} + \frac{1}{5}P_{k - 1} + \frac{3}{5}L_{k - 1} \end{cases}$$
Sottraendo la seconda dalla terza ricaviamo
$$L_k - P_k = \frac{1}{5}S_{k - 1} - \frac{1}{5}L_{k - 1} \qquad (\star)$$
Dalla terza, shiftando gli indici, si ha $P_k = 5L_{k + 1} - S_k - 3L_k$ e, sostituendo in $(\star)$:
$$4L_k = 5L_{k + 1} - S_k + \frac{1}{5}S_{k - 1} - \frac{1}{5}L_{k - 1}$$
da cui
$$25L_{k + 2} - 20L_{k + 1} - L_k - 5S_{k + 1} + S_k = 0 \qquad (\blacklozenge)$$
Dalla prima otteniamo una scrittura di $L_k$ in funzione di $S$: $L_k = \frac{5}{4}S_{k + 1} - \frac{1}{4}S_k$. Sostituendo quest'ultima in $(\blacklozenge)$ (shiftando opportunamente gli indici) ricaviamo infine
$$25S_{k + 3} - 25S_{k + 2} - S_{k + 1} + S_k = 0 \qquad (\lozenge)$$
Da qui in poi è tutta teoria standard sulle successioni per ricorrenza lineari. L'equazione caratteristica associata a $(\lozenge)$ è
$$25x^3 - 25x^2 - x + 1 = 0 \Leftrightarrow (x - 1)(5x - 1)(5x + 1) = 0$$
le cui radici sono $1$ e $\pm \frac{1}{5}$. Si ha dunque $S_k = \lambda + \mu\left(\frac{1}{5}\right)^k + \nu\left(-\frac{1}{5}\right)^k$ per opportune costanti $\lambda$, $\mu$ e $\nu$ che ora determiniamo nel solito modo. Troviamo a mano che $S_0 = S_1 = 0$, $S_2 = \frac{4}{25}$, da qui impostiamo il sistema
$$\begin{cases} \lambda + \mu + \nu = 0 \\ \lambda + \frac{1}{5}\mu - \frac{1}{5}\nu = 0 \\ \lambda + \frac{1}{25}\mu + \frac{1}{25}\nu = \frac{4}{25} \end{cases}$$
che ha soluzione $\lambda = \frac{1}{6}$, $\mu = -\frac{1}{2}$, $\nu = \frac{1}{3}$.
Dunque la probabilità cercata è $\displaystyle S_k = \frac{1 - 3\left(\frac{1}{5}\right)^k + 2\left(-\frac{1}{5}\right)^k}{6}$.

[AlexThirty]

Scusa cip ma non capisco come definisci L, S, e P. Faccio confusione con partenze e arrivi

[cip999]

$X_k$ (dove al posto di $X$ metti $S$, $P$ ed $L$) è la probabilità che la mosca, partendo dalla parete il cui nome inizia con $X$ e muovendosi $k$ volte in modo del tutto casuale, si ritrovi alla fine sul pavimento.
Con questa notazione, ti viene chiesto di trovare un'espressione esplicita $S_k$ e, ad esempio, si ha che $S_0 = L_0 = 0$ (partendo dal soffitto o da una parete laterale, non puoi raggiungere il pavimento senza muoverti) e $P_0 = 1$.

[Drago96]

Non so perché hai scelto questa buffa notazione, e non è l'ora di mettermi a controllare per bene, ma il risultato finale è sbagliato... forse potrebbe essere che $S_2=4/25$
Domani tento una soluzione in ogf, credo venga fuori una cosa figa...

[Hawk]

Metto la soluzione che ho scritto io.
In sintesi, se indichiamo $ p_k $ indica la probabilità della mosca di trovarsi sul pavimento dopo k mosse, con $ s_k $ la probabilità di trovarsi sul soffitto dopo k mosse, $ q_k $ la probabilità di trovarsi sulle pareti laterali dopo k mosse, si riesce a ricavare che valgono:
$ p_k=\frac{1}{5}p_{k-1}+\frac{1}{5}q_{k-1} $ e
$ q_k=\frac{3}{5}q_{k-1}+\frac{4}{5}(1-q_{k-1}) $ ora notiamo che $ q_1=\frac{4}{5} $ e seguendo la ricorsione vale $ q_2=\frac{16}{25} $ possiamo scrivere quindi l'equazione, un po' come fatto da cip, per ricavare il termine generale della sequenza che vale $ q_k=(\frac{4}{5})^k $.
In definitiva vale $ p_k=\frac{1}{5}p_{k-1}+\frac{1}{5}(\frac{4}{5})^k $ bisogna ora utilizzare il suggerimento del testo del problema per concludere.

Alla fine a me veniva $ p_k=-\frac{16}{15}(\frac{1}{5})^k+\frac{4}{15}(\frac{4}{5})^k $

[RiccardoKelso]

Scusate ma dopo venti minuti di smadonnamenti vari per via di questo LaTeX mi rassegno e scrivo in modo nabbo. Comunque la formula finale non dovrebbe essere -(1/6)*(1/25)^k + 1/6 dove k è il numero di mosse/2 se pari e il (numero di mosse diminuito di uno)/2 se dispari?

[cip999]

@Drago: più che giusto, nessuna delle quattro pareti della stanza è crollata durante la risoluzione del problema... Spero che ora vada bene, il check a mano con il caso $k = 3$ (che in realtà avevo fatto anche ieri, commettendo lo stesso errore e ottenendo dunque una falsa conferma) sembra positivo.
Comunque aspetto la soluzione con le ogf, l'argomento mi interessa non poco...

[Mountains Drew]

...
$ q_k=\frac{3}{5}q_{k-1}+\frac{4}{5}(1-q_{k-1}) $ ora notiamo che $ q_1=\frac{4}{5} $ e seguendo la ricorsione vale $ q_2=\frac{16}{25} $ possiamo scrivere quindi l'equazione, un po' come fatto da cip, per ricavare il termine generale della sequenza che vale $ q_k=(\frac{4}{5})^k $.

$q_k=\left(\frac45\right)^k$ funziona solo per k=1,2. Per 3 non funziona già più. (ma anche per k=0 ...). La formula corretta per quella ricorrenza sarebbe $\frac23\left(1-\left(-\frac15\right)^k\right)$.

Scusate ma dopo venti minuti di smadonnamenti vari per via di questo LaTeX mi rassegno e scrivo in modo nabbo. Comunque la formula finale non dovrebbe essere -(1/6)*(1/25)^k + 1/6 dove k è il numero di mosse/2 se pari e il (numero di mosse diminuito di uno)/2 se dispari?

Anche io ho ottenuto questo risultato, che è equivalente a quello di cip.
Già che ci sono dico come ho fatto.

Testo nascosto:

$s_k$:= probabilità che la mosca alla k-esima mossa atterri sul soffitto (sempre partendo dal soffitto)
$p_k$:= probabilità che la mosca alla k-esima mossa atterri sul pavimento (sempre partendo dal soffitto)
$m_k$:= probabilità che la mosca alla k-esima mossa atterri su uno dei muri laterali (sempre partendo dal soffitto)
sapendo che per ovvi motivi $p_k+m_k+s_k = 1 $, le ricorrenze (che ci interessano) sono
$$ \begin{cases}
s_{k+1} = \frac15 m_k + \frac15 s_k=\frac15 (m_k+s_k)= \frac15 (1-p_k) \\
p_{k+1} = \frac15 m_k + \frac15 p_k =\frac15 (m_k+p_k)= \frac15 (1-s_k)\\
\end{cases}$$
sostituendo la prima nella seconda (shiftando gli indici) si ha $p_{k}=\frac15 \left(1- \frac15 (1-p_{k-2})\right) = \frac1{25}p_{k-2}+\frac4{25}$
Quindi la ricorrenza è di 2 in 2 e $p_0=p_1=0$ ed è una semplice ricorrenza lineare con dipendenza da un solo termine.
Quindi con qualche passaggio si ottiene $ p_{2n}=p_{2n+1}= \frac{1-\left(\frac15\right)^{n}}{6}$, quindi
$$ p_{k}= \frac{1-\left(\frac1{25} \right)^{\lfloor \frac k2 \rfloor}}{6} $$

[cip999]

$\lfloor k\rfloor$ non è che abbia tanto senso, penso intendessi $2\left\lfloor\frac{k}{2}\right\rfloor$.
Comunque una volta trovata la ricorrenza che descrive $p$, in alternativa la si può traslare (ad esempio ponendo $q_k = p_k - \frac{1}{6}$, che verifica la ricorrenza $q_k = \frac{1}{25}q_{k - 2}$) e risolvere come una successione per ricorrenza lineare standard, ottenendo $q_k = -\frac{1}{2}\left(\frac{1}{5}\right)^k + \frac{1}{3}\left(-\frac{1}{5}\right)^k$ e quindi, ritraslando, $p_k = \frac{1}{6} - \frac{1}{2}\left(\frac{1}{5}\right)^k + \frac{1}{3}\left(-\frac{1}{5}\right)^k$, che è esattamente quella che ho trovato sopra.
Però in effetti così è tutto molto più rapido...

[Mountains Drew]

Sì, è come hai detto tu. Ora ho corretto. Avevo fatto confusione con gli indici

[Drago96]

Anche se non strettamente necessario, mostro una soluzione con le generatrici, utile in casi più generali, dato che alla fine si tratta solo di risolvere un sistema di $n$ equazioni in $n$ incognite.
Alur, chiamiamo $p_i,s_i,l_i$ la probabilità di essere su pavimento, soffitto, pareti laterali alla $i$-esima mossa. Abbiamo dunque $$\begin{cases}s_{i+1}=s_i/5+l_i/5 \\ p_{i+1}=p_i/5+l_i/5 \\ l_{i+1}=4s_i/5+4p_i/5+3l_i/5\end{cases}$$
Ora moltiplichiamo tutto per $x^i$ e facciamo la somma su tutti i naturali. Se chiamiamo $\displaystyle P(x)=\sum_{i\ge0}p_ix^i$ e simili, osserviamo che $\sum_{i\ge0}p_{i+1}x^i=\frac{P(x)}x$ in quanto $p_0=0$; similmente $\sum_{i\ge0}l_{i+1}x^i=\frac{L(x)}x$ e $\sum_{i\ge0}s_{i+1}x^i=\frac{S(x)-1}x$ perché $s_0=1$.
Il sistema dunque si riscrive come $$\begin{cases}\frac{S-1}x=S/5+L/5 \\ \frac P x=P/5+L/5 \\\frac L x=4S/5+4P/5+3L/5\end{cases}$$
Osserviamo che $S+P+L=\frac1{1-x}$ perché $s_i+p_i+l_i=1\forall i$.
La terza equazione si riscrive come $5L=4x(\frac1{1-x}-L)+3Lx$ da cui $\displaystyle L=\frac{4x}{(1-x)(x+5)}$
Sostituiamo nella seconda: $5P=xP+Lx$ ovvero $\displaystyle P(5-x)=\frac{4x^2}{(1-x)(x+5)}$ e riscrivendo per bene $$\displaystyle P(x)=\frac{4x^2/25}{(1-x)(1+\frac1 5x)(1-\frac1 5x)}$$
Infine spezziamo $P$ in frazioni semplici: $\displaystyle P(x)=\frac1 6\cdot\frac1{1-x}-\frac1 2\cdot\frac1{1-\frac1 5x}+\frac1 3\cdot\frac1{1+\frac1 5x}$
Che dà la formula generale già trovata

P.S: penso sia noto, ma se risolvete il sistema delle ricorrenze ignorando gli indici (ovvero facendo finta che $p_{i+1}=p_i$) sperabilmente ottenete la stima asintotica di ciascuna probabilità... o meglio, se quelle probabilità tendono ad un limite, allora è quello che trovate risolvendo il sistema lineare.