SNS 2015 - 2

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

SNS 2015 - 2

Messaggio da Drago96 » 29 ago 2015, 18:50

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?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

matpro98
Messaggi: 455
Iscritto il: 22 feb 2014, 18:42

Re: SNS 2015 - 2

Messaggio da matpro98 » 29 ago 2015, 20:55

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

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: SNS 2015 - 2

Messaggio da Drago96 » 29 ago 2015, 21:06

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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: SNS 2015 - 2

Messaggio da cip999 » 29 ago 2015, 22:49

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}$.
Ultima modifica di cip999 il 30 ago 2015, 11:04, modificato 1 volta in totale.
- E cosa c'è di peggio del suicidio?
- La vita.

AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: SNS 2015 - 2

Messaggio da AlexThirty » 30 ago 2015, 00:37

Scusa cip ma non capisco come definisci L, S, e P. Faccio confusione con partenze e arrivi
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: SNS 2015 - 2

Messaggio da cip999 » 30 ago 2015, 01:17

$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$.
- E cosa c'è di peggio del suicidio?
- La vita.

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: SNS 2015 - 2

Messaggio da Drago96 » 30 ago 2015, 01:36

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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: SNS 2015 - 2

Messaggio da Hawk » 30 ago 2015, 02:07

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 $
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

RiccardoKelso

Re: SNS 2015 - 2

Messaggio da RiccardoKelso » 30 ago 2015, 09:55

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
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: SNS 2015 - 2

Messaggio da cip999 » 30 ago 2015, 11:18

@Drago: più che giusto, nessuna delle quattro pareti della stanza è crollata durante la risoluzione del problema... :lol: 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...
- E cosa c'è di peggio del suicidio?
- La vita.

Mountains Drew
Messaggi: 59
Iscritto il: 25 mag 2013, 16:41
Località: Bregnano (Provincia di Como)

Re: SNS 2015 - 2

Messaggio da Mountains Drew » 30 ago 2015, 16:02

Hawk ha scritto: ...
$ 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)$.
RiccardoKelso ha scritto: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} $$
Ultima modifica di Mountains Drew il 30 ago 2015, 19:35, modificato 1 volta in totale.

cip999
Messaggi: 148
Iscritto il: 26 nov 2013, 14:44

Re: SNS 2015 - 2

Messaggio da cip999 » 30 ago 2015, 17:08

$\lfloor k\rfloor$ non è che abbia tanto senso, penso intendessi $2\left\lfloor\frac{k}{2}\right\rfloor$. :P
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... :)
- E cosa c'è di peggio del suicidio?
- La vita.

Mountains Drew
Messaggi: 59
Iscritto il: 25 mag 2013, 16:41
Località: Bregnano (Provincia di Como)

Re: SNS 2015 - 2

Messaggio da Mountains Drew » 30 ago 2015, 19:47

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

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: SNS 2015 - 2

Messaggio da Drago96 » 30 ago 2015, 20:46

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.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Rispondi