- 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
SNS 2015 - 2
SNS 2015 - 2
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:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: SNS 2015 - 2
Tutte le probabilità sono uguali, è davvero così semplice??
Re: SNS 2015 - 2
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)
Re: SNS 2015 - 2
Testo nascosto:
Ultima modifica di cip999 il 30 ago 2015, 11:04, modificato 1 volta in totale.
-
- Messaggi: 217
- Iscritto il: 20 giu 2015, 20:58
Re: SNS 2015 - 2
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.
-"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.
Re: SNS 2015 - 2
$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$.
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$.
Re: SNS 2015 - 2
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...
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)
Re: SNS 2015 - 2
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 $
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. »
Re: SNS 2015 - 2
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?
Re: SNS 2015 - 2
@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...
Comunque aspetto la soluzione con le ogf, l'argomento mi interessa non poco...
-
- Messaggi: 59
- Iscritto il: 25 mag 2013, 16:41
- Località: Bregnano (Provincia di Como)
Re: SNS 2015 - 2
$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)$.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 $.
Anche io ho ottenuto questo risultato, che è equivalente a quello di cip.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?
Già che ci sono dico come ho fatto.
Testo nascosto:
Ultima modifica di Mountains Drew il 30 ago 2015, 19:35, modificato 1 volta in totale.
Re: SNS 2015 - 2
$\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...
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...
-
- Messaggi: 59
- Iscritto il: 25 mag 2013, 16:41
- Località: Bregnano (Provincia di Como)
Re: SNS 2015 - 2
Sì, è come hai detto tu. Ora ho corretto. Avevo fatto confusione con gli indici
Re: SNS 2015 - 2
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.
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)