Successione lineare

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Successione lineare

Messaggio da marconato »

Ciao a tutti, stamattina mi è venuto in mente questo problema e ho provato a risolverlo :)
Purtoppo non sono molto pratico delle successioni con dipendenza da più termini quindi lo metto qui!

"Alberto pensa ad un numero naturale \(n\) e lo scrive su un foglio. Poi lancia una moneta, se esce testa incrementa il numero di uno se esce croce lo decrementa. Qual'è la probabilità che dopo \(m\) lanci, con \(m \geq n\) il numero scritto nel foglio sia 0?"
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Successione lineare

Messaggio da Drago96 »

In realtà qua non ti serve nessuna successione (anche se non escludo ci sia una successione che risolve il problema), e chiedendo un probabilità il problema è di combinatoria ;)
Provo a darti un paio di hint:
Affinché il numero sia $0$, quante teste e quante croci devono uscire?
Stabilito il numero di teste, diciamo $k$, qual è la probabilità che su $m$ lanci escano $k$ teste?

Quest'ultima domanda è un fatto noto di teoria, che in generale determina la probabilità che si verifichino $a$ successi su un totale di $b$ prove, e in ciascuna prova la probabilità di successo (indipendente dalle altre prove) è $p$.
Ti suggerisco anche di trovare la risposta a questa domanda, perché ti potrebbe servire in futuro! :D
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Azz è vero! se vedevo il problema in questo modo era molto più semplice. L'ho messo in algebra perchè pensavo fosse necessario utilizzare una successione lineare con dipendenza da due termini precedenti ma ho cannato in pieno!
Comunque ecco la soluzione:

Scriviamo \(m = n + 2k\), abbiamo che se vogliamo che dopo esattamente \(m\) lanci si ottenga \(0\) devono uscire esattamente \(n + k\) croci.
Questo è possibile in \({n + 2k \choose n + k}\) modi su un totale di \(2^{n + 2k}\) possibili casi, quindi la probabilità cercata è \[{n + 2k \choose n + k}\frac{1}{2^{n + 2k}} = \prod_{i = n + k + 1}^{n + 2k}i\cdot\frac{1}{k!2^{n + 2k}}\]
Si noti che se \(m - n\) è dispari, \(k\) non è intero e quindi non è possibile arrivare esattamente a \(0\) dopo \(m\) lanci.

Vado a mangiare poi la ricontrollo, spero sia giusta! xD
Ultima modifica di marconato il 03 lug 2013, 20:50, modificato 1 volta in totale.
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Mi sono dimenticato di specificare che tale ragionamento è applicabile perchè ogni sequenza di testa croce è equiprobabile alle altre.
Variante del problema: cosa cambia se la probabilità che esca testa non è \(\frac{1}{2}\) ma \(p \neq \frac{1}{2}, 0 < p < 1\)?

Riscrivo quindi il problema in versione hard.
"Alberto pensa un numero \(n\) e lo scrive su un foglio, poi tira \(m\) volte una moneta truccata che da testa con probabilità \(q\) e croce con probabilità \(1-q\). Se ogni volta che esce testa Alberto incrementa il numero e ogni volta che esce croce lo decrementa, qual'è la probabilità che dopo esattamente \(m\) lanci il numero sia \(0\)?"

Tentativo di impostazione del problema con una successione (spero vivamente che anche adesso si possa fare in un modo più semplice :( )
Testo nascosto:
Chiamo \(p(i,j)\) la probabilità che dopo esattamente \(i\) lanci il numero scritto sia \(j\).
Chiamiamo \(q\) la probabilità che esca testa (incremento) e quindi la probabilità che esca croce (decremento) è \(1 - q\).
Abbiamo che \(p(i,j) = q\cdotp(i-1,j-1) + (1-q)\cdotp(i-1,j+1)\).
Possiamo fare delle considerazioni:
1) Se vogliamo calcolare la probabilità che dopo esattamente \(m\) lanci il numero scritto sia \(0\) abbiamo come prima che \(n-m\) deve essere pari.
Questa condizione può essere estesa in senso più generale dicendo che \(p(i,j) \neq 0 \implies i \cong j - n (mod 2)\) ossia che se \(j - n\) non ha la stessa parità di \(i\) allora \(p(i,j) = 0\)
2) Abbiamo che \(p(i,j) = 0 \forall j < n - i \land j > n + i\)
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Mi rispondo da solo! In realtà si poteva fare anche questo punto senza la succesione.
Abbiamo come prima che devono uscire \(n + k\) croci e \(k\) teste, con \(k\) naturale e \(k = \frac{m - n}{2}\).
Quindi utilizzando la variabile casuale binomiale \(X\), dove
\(X(i) =\) probabilità che dopo i lanci il numero sia 0
abbiamo che \[X(n) = q^{k}(1-q)^{n+k}{n+2k \choose n+k}\]
Si noti che per \(q=\frac{1}{2}\) il risultato è identico a quello di prima.
Prima avevo considerato la probabilità come casi favorevoli su casi possibili, dato che ogni caso era equiprobabile.
Ora che ogni caso non è equiprobabile ho utilizzato la distribuzione binomiale e tutto viene lo stesso :)
Ultima modifica di marconato il 05 lug 2013, 17:12, modificato 1 volta in totale.
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Successione lineare

Messaggio da Drago96 »

Molto bene, nel tuo monologo hai detto tutte cose giuste! :D
E sapevi anche la distribuzione binomiale! :P
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Sisi, mi ero intestardito a vederla come una sucessione per ricorrenza xD comunque secondo te la "successione" che ho impostato dentro lo spoiler è risolvibile in metodi umani (stile successione dipendente da due termini precedenti (pag 29 schede olimpiche Gobbino))?
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Successione lineare

Messaggio da Triarii »

C'era un problema di probabilità di un Cesenatico vecchiotto (mi pare 1995) dove venivano usate delle successioni i cui termini dipendevano da quelli precedenti. Non veniva però usato il formulazzo per il termine generico nelle soluzioni perchè si poteva fare tranquillamente a mano (inoltre credo che non si potessero nemmeno utilizzare visto che diventavano per ricorrenza dal secondo o terzo passo in poi, non ricordo bene)
http://andfog.altervista.org/math/Cesen ... Ben%5D.pdf Dovrebbe essere il 3, vedi se ce la fai a risolverlo :D
"We' Inge!"
LTE4LYF
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Perfetto allora apro il topic su probabilità, oggi sono via, domani provo a risolverlo. :mrgreen:
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Successione lineare

Messaggio da Gottinger95 »

Si, c'è un modo umano! Pensa sto facendo la stessa cosa ma sul problema dei compleanni, ossia qual'è la probabilità che su \(n\) persone \(k\) facciano il compleanno in uno stesso giorno fissato. Poi per ottenere la condizione "in un giorno qualsiasi" si applica principio di inclusione-esclusione su \(p(n,k,m) =\) probabilità che tra \(n\) persone in \(m\) giorni fissati \(k\) facciano il compleanno lo stesso giorno. Questo comunque è un altro problema.

Per questo, prova così (io perlomeno l'ho fatto così): immagina un piano cartesiano in cui \(p(n,k)\) è rappresentato dal punto \((n,k)\). In pratica, quando vai a domandare al punto \((n,k)\) qual'è la sua probabilità, lui lo va a chiedere a \((n-1,k)\) e \((n-1,k-1)\), dunque pesa le loro risposte con \(q,1-q\). Di domanda in domanda, si forma una sorta di reticolo generato dai vettorini \((-1,-1)\) e \((-1,0)\) (quelli che portano da \((n,k)\) agli altri due), e a ogni vettore è associato un peso.
Per risolvere la ricorrenza devi capire 3 cose:
1. Di domanda in domanda, alla fine del processo quali punti vengono interrogati?
2. In quanti modi puoi arrivare ai punti da interrogare dal punto \(n,k\) (n.b: se \(A,B\) sono due punti finali, i cammini che arrivano a B e passano per A non vanno contati, perchè il "ciclo di domande" termina con il punto A)?
3. Quale "peso" è associato ai cammini dai punti da interrogare al punto \((n,k)\)?
Ah, ti conviene porre 0 i punti appena fuori dal campo di esistenza della ricorrenza (apparte \((0,0)\) che vale 1) e "interrogare" anche loro: i conti vengono estremamente più facili. Spero di essermi spiegato. Se capisci, sarai soddisfatto perchè si risolve in mezzo secondo :)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Chiarissimo, davvero una bella idea! Ecco i miei ragionamenti (attento che i vettori sono \((-1,-1)\) e \((-1,+1)\).
I punti hanno coordinate \(m,n\). \(m\) indica il numero di lanci che è stato effettuato per ottenere il numero mentre \(n\) il numero scritto sulla lavagna.
Si parte da \((0,N)\) ossia al lancio \(0\) il numero scritto è \(N\) e si arriva a \((M,0)\) ossia al lancio \(M\) il numero scritto deve essere 0.
Immagine
Dal disegno si nota che viene fuori un rettangolo di misure \(N+K\), \(K\). Dove \(K = \frac{M - N}{2}\).
Dal disegno si notano entrambe le proprietà che ho descritto sopra, cioè.
Per arrivare da un punto ad un altro ci sono svariati percorsi, pertanto la probabilità di arrivare da un punto ad un altro è uguale alla probabilità de punto a cui punta il vettore pesato moltiplicato per il peso del vettore.
Poiché da un punto partono due vettori e non si possono percorrere entrambi contemporaneamente accade che la probabilità di arrivare in quel punto è la probabilità di arrivare attraverso il primo vettore più la probabilità di arrivare attraverso il secondo vettore (eventi incompatibili quindi si somma la probabilità).
In conclusione la probabilità di arrivare in un punto a partire da un punto è pari alla somma della probabilità di ciascun percorso che arriva in quel punto.
Si nota che per arrivare da un punto ad un punto, qualsiasi sia il percorso il numero di vettori dell'uno e dell'altro tipo da attraversare dipende solo dal punto di partenza e di arrivo.
Pertanto la probabilità di arrivare a \((M,0)\) partendo da \((0,N)\) è pari al peso dei vettori \((-1,-1)\) cioè \(q\) elevato al numero degli stessi, moltiplicato al peso dei vettori \((-1,+1)\), cioè \(1-q\) elevato al numero degli stessi.
In totale quindi risulta \(q^K(1-q)^(N+K)\)
Questo valore va moltiplicato per il numero dei percorsi che collegano \((0,N)\) e \((M,0)\) e dal calcolo combinatorio esso risulta essere \({n + 2k \choose n + k}\).
Si ottiene quindi lo stesso risultato di prima.
E' quello che volevi dire te giusto?
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Successione lineare

Messaggio da Gottinger95 »

Esattamente questo! Guarda, se vuoi sto facendo una ricerca proprio sulle ricorrenze interpretate diciamo geometricamente, potremmo lavorarci un po' insieme! Vedo che l'idea ti è piuttosto chiara, generalizzarla per tante variabili e tanti vettori è un attimo, basta stare attenti a certe condizioni che devono verificarsi.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
marconato
Messaggi: 34
Iscritto il: 13 mag 2013, 15:14

Re: Successione lineare

Messaggio da marconato »

Volentieri, il mio numero ce l'hai :)
Rispondi