Passeggiate pericolose...
Ecco un problema di probabilità a mio avviso molto carino.Un ubriaco si trova sul ciglio di un precipizio,ed avanza nella direzione del burrone con probabilità 1/3 ed indietreggia con probabilità 2/3.Si trova a 2 passi prima del precipizio.Qual'è la probabilità che alla fine cada?
Risposte
trattasi di passeggiata aleatoria non simmetrica modellizzabile con una catena di markov a tempo discreto. nel caso in questione gli stati sono tutti transienti. per calcolare la probabilità suddetta basta rendere lo stato 2 (quello in cui si cade) uno stato assorbente e calcolare la prob di assorbimento.
non è difficile da fare perchè viene una semplice sommatoria impostando il sistemino con tutte le h(i)[A] (prob partendo dallo stato i di raggiungere il sottoinsieme A dello spazio degli stati) ma ora non ho tempo di fare i conti.
basta imporre h(2)=1
h(1)=1/3+2/3h(0)
h(0)=1/3h(1)+2/3h(-1)
h(-1)=1/3h(0)+2/3h(-2)
...
trovare la relazione ricorsiva e risolvere per h(0)
Modificato da - Maverick il 07/05/2004 21:38:40
non è difficile da fare perchè viene una semplice sommatoria impostando il sistemino con tutte le h(i)[A] (prob partendo dallo stato i di raggiungere il sottoinsieme A dello spazio degli stati) ma ora non ho tempo di fare i conti.
basta imporre h(2)=1
h(1)=1/3+2/3h(0)
h(0)=1/3h(1)+2/3h(-1)
h(-1)=1/3h(0)+2/3h(-2)
...
trovare la relazione ricorsiva e risolvere per h(0)
Modificato da - Maverick il 07/05/2004 21:38:40
mi sono fatto un po' di conti oggi mentre ero in treno e tornavo verso casa.
mi viene 13/77
boh...
mi viene 13/77
boh...
Non so che dirti...io a suo tempo mi impelagai in una caterva di conti e in una serie che non riuscivo a sommare.Cercai di risolvere il prob con metodi elementari perchè non conoscevo(e non conosco)i metodi che hai utilizzato.Se non mi ricordo male comunque al denominatore compariva un 7...so che è poco però..
bah, a questo punto aspettiamo che qualcun altro si cimenti...
Interessante questa variante del problema delle ‘passeggiate a caso’, soprattutto perché a prima vista pare complesso ma la sua soluzione si rivela poi sorprendentemente semplice…
Cominciamo verificando che l’ubriaco, partendo da un punto di ordinata y=0, giunge ad attraversare la retta di ordinata y=+ 2 [precipitando quindi nel baratro…] necessariamente dopo un numero pari di passi [che indicheremo con 2*(n+1)…], dei quali gli ultimi sono stati eseguiti avanzando due volte in direzione del baratro partendo da un punto di ordinata y=0. Indichiamo ora con p la probabilità di avanzare di un passo in senso positivo [cioè verso il baratro…] e con q=1-p la probabilità di avanzare in senso negativo [allontanandosi quindi dal baratro…]. La probabilità dunque che dopo 2*(n+1) passi l’ubriaco precipiti nel baratro sarà dunque…
P(n)= p^2 * K(n) * (p*q)^n (1)
… ove con K(n) abbiamo indicato il numero di traiettorie possibili che partendo dall’ordinata y=0 giungono dopo 2*n passi ancora all’ordinata y=0 senza superare mai l’ordinata y=1. K(n) a sua volta può essere scomposto in due termini, vale a dire…
K(n)=K+(n)+K-(n) (2)
... dove K+ è il numero di traiettorie che iniziano ‘in salita’ e K- il numero di traiettorie che iniziano ‘in discesa’. Non è difficile verificare che è…
K+(n)=2^(n-1)
K-(n)= K(n-1) (3)
... per cui si ottiene facilmente…
K(n)=2^n (4)
La probabilità che l’ubriaco ‘prima o poi’ precipiti è data pertanto da…
P=p^2*
[n=0,+00] 2^n*(p*q)^n = p^2*1/(1-2*p*q) (5)
Nel caso ‘più comune’ in cui p=q=1/2 sarà P=1/4*1/(1-1/2)=1/2. Nel caso indicato dal problema è p=1/3 e q=2/3, per cui sarà P=1/9*1/(1-4/9)=1/5. Se invece è p=2/3 e q=1/3 sarà P=4/9*1/(1-4/9)=4/5. E’ possibile naturalmente esaminare altri casi e tracciare un grafico di P al variare di p...
cordiali saluti!...
lupo grigio
Cominciamo verificando che l’ubriaco, partendo da un punto di ordinata y=0, giunge ad attraversare la retta di ordinata y=+ 2 [precipitando quindi nel baratro…] necessariamente dopo un numero pari di passi [che indicheremo con 2*(n+1)…], dei quali gli ultimi sono stati eseguiti avanzando due volte in direzione del baratro partendo da un punto di ordinata y=0. Indichiamo ora con p la probabilità di avanzare di un passo in senso positivo [cioè verso il baratro…] e con q=1-p la probabilità di avanzare in senso negativo [allontanandosi quindi dal baratro…]. La probabilità dunque che dopo 2*(n+1) passi l’ubriaco precipiti nel baratro sarà dunque…
P(n)= p^2 * K(n) * (p*q)^n (1)
… ove con K(n) abbiamo indicato il numero di traiettorie possibili che partendo dall’ordinata y=0 giungono dopo 2*n passi ancora all’ordinata y=0 senza superare mai l’ordinata y=1. K(n) a sua volta può essere scomposto in due termini, vale a dire…
K(n)=K+(n)+K-(n) (2)
... dove K+ è il numero di traiettorie che iniziano ‘in salita’ e K- il numero di traiettorie che iniziano ‘in discesa’. Non è difficile verificare che è…
K+(n)=2^(n-1)
K-(n)= K(n-1) (3)
... per cui si ottiene facilmente…
K(n)=2^n (4)
La probabilità che l’ubriaco ‘prima o poi’ precipiti è data pertanto da…
P=p^2*
[n=0,+00] 2^n*(p*q)^n = p^2*1/(1-2*p*q) (5)Nel caso ‘più comune’ in cui p=q=1/2 sarà P=1/4*1/(1-1/2)=1/2. Nel caso indicato dal problema è p=1/3 e q=2/3, per cui sarà P=1/9*1/(1-4/9)=1/5. Se invece è p=2/3 e q=1/3 sarà P=4/9*1/(1-4/9)=4/5. E’ possibile naturalmente esaminare altri casi e tracciare un grafico di P al variare di p...
cordiali saluti!...
lupo grigio
Ciao lupo.Non mi è chiara la seconda della (3) se intendevi k-(n)=k*(n-1),allora è sbagliata perchè secondo le tue notazioni k-(n)
n=1 (+-) (-+) e si ha k(1)=2=2^1
n=2 (+-+-) (-+-+) (--++) (+--+) e di nuovo k(2)=2^2=4
ma per n=3:
(+-+-+-) (+-+--+) (+---++) (+--+-+) (---+++) (-+-+-+) (-+--++) (--+++--) (--+-++)
queste sono già 9 ma ne rimangono altre.A suo tempo trovai una relazione ricorsiva tra k(n+1) e k(n) che però coinvolgeva binomiali.
Ciao.
n=1 (+-) (-+) e si ha k(1)=2=2^1
n=2 (+-+-) (-+-+) (--++) (+--+) e di nuovo k(2)=2^2=4
ma per n=3:
(+-+-+-) (+-+--+) (+---++) (+--+-+) (---+++) (-+-+-+) (-+--++) (--+++--) (--+-++)
queste sono già 9 ma ne rimangono altre.A suo tempo trovai una relazione ricorsiva tra k(n+1) e k(n) che però coinvolgeva binomiali.
Ciao.
lupo grigio ci deve essere qualcosa che non va nel ragionamento.
non ho il tempo di esaminarlo bene perchè ho un esame domani, ma di sicuro posso dirti che se la passeggiata è simmetrica la probabilità che cada nel burrone è 1, cioè cade sicuramente visto che la probabilità di primo passaggio in un tempo finito è 1 per qualunque stato di una catena ricorrente. (anche se in questo caso è ricorrente nulla).
non ho il tempo di esaminarlo bene perchè ho un esame domani, ma di sicuro posso dirti che se la passeggiata è simmetrica la probabilità che cada nel burrone è 1, cioè cade sicuramente visto che la probabilità di primo passaggio in un tempo finito è 1 per qualunque stato di una catena ricorrente. (anche se in questo caso è ricorrente nulla).
In effetti l’osservazione di cart è esatta [o meglio ‘quasi-esatta’…] e il problema è un poco più complesso di quello che avevo supposto all’inizio. Il miglior modo di dare risposta a cart, e anche alla questione sollevata da Maverick, consiste quindi in una corretta impostazione del problema…
Ferme restando le ipotesi fatte in precedenza indichiamo sempre con K(n) il numero di traiettorie che, partendo da un punto di ordinata y=0 raggiungono dopo 2*n passi un punto anch’esso di ordinata y=0 senza mai oltrepassare l’ordinata y=1. Supponendo di conoscere K(n) proviamo a determinare, seguendo la traccia proposta da cart, in quante maniere si possono ‘prolungare’ le K(n) traiettorie di 2*n passi di altri due passi in modo da raggiungere dopo 2*(n+1) passi nuovamente un punto di ordinata y=0. Innanzitutto posso osservare che tutte le K(n) traiettorie possono essere ‘prolungate’ in due modi, vale a dire aggiungendo la sequenza +- oppure -+ e questo significa 2*K(n) traiettorie. Le K(n-1) traiettorie terminanti in y=0 dopo 2*(n-1) passi possono poi tutte essere prolungate con la sequenza --++ e questo vuol dire altre k(n-1) traiettorie. In modo analogo le K(n-2) traiettorie terminanti in y=0 dopo 2*(n-2) passi possono tutte essere prolungate con la sequenza ---+++ e questo porta altre K(n-2) traiettorie. Proseguendo con il ragionamento si arriva alla seguente formula ricorsiva…
K(n+1) = 2*K(n) +[i=0,n-1] K(i) (1)
Riporto qui i primi valori di K(i)…
K(0)=1
K(1)=2 [+-] [-+]
K(2)=5 [+-+-] [+--+] [-+-+] [-++-] [--++]
K(3)=13 [+-+-+-] [+--++-] [-+-++-] [-++-+-] [--+++-] [+-+--+] [+--+-+][-+-+-+] [--++-+] [+---++] [-+--++] [+---++] [---+++]
… e quindi altri ancora…
K(4)= 34
K(5)= 89
K(6)= 233
K(7)= 610
K(8)= 1597
K(9)= 4181
K(10)= 10946
Una volta stabilite le K(n) la probabilità cercata si dovrebbe ottenere dalla formula…
P= p^2 * [n=0,+00] K(n)*(p*q)^n (2)
A questo punto [memore della cattiva strada intrapresa in precedenza…]mi fermerei un poco in attesa, se ve ne sono, di osservazioni da parte vostra…
cordiali saluti!…
lupo grigio
Modificato da - lupo grigio il 13/05/2004 11:22:28
Ferme restando le ipotesi fatte in precedenza indichiamo sempre con K(n) il numero di traiettorie che, partendo da un punto di ordinata y=0 raggiungono dopo 2*n passi un punto anch’esso di ordinata y=0 senza mai oltrepassare l’ordinata y=1. Supponendo di conoscere K(n) proviamo a determinare, seguendo la traccia proposta da cart, in quante maniere si possono ‘prolungare’ le K(n) traiettorie di 2*n passi di altri due passi in modo da raggiungere dopo 2*(n+1) passi nuovamente un punto di ordinata y=0. Innanzitutto posso osservare che tutte le K(n) traiettorie possono essere ‘prolungate’ in due modi, vale a dire aggiungendo la sequenza +- oppure -+ e questo significa 2*K(n) traiettorie. Le K(n-1) traiettorie terminanti in y=0 dopo 2*(n-1) passi possono poi tutte essere prolungate con la sequenza --++ e questo vuol dire altre k(n-1) traiettorie. In modo analogo le K(n-2) traiettorie terminanti in y=0 dopo 2*(n-2) passi possono tutte essere prolungate con la sequenza ---+++ e questo porta altre K(n-2) traiettorie. Proseguendo con il ragionamento si arriva alla seguente formula ricorsiva…
K(n+1) = 2*K(n) +
[i=0,n-1] K(i) (1)Riporto qui i primi valori di K(i)…
K(0)=1
K(1)=2 [+-] [-+]
K(2)=5 [+-+-] [+--+] [-+-+] [-++-] [--++]
K(3)=13 [+-+-+-] [+--++-] [-+-++-] [-++-+-] [--+++-] [+-+--+] [+--+-+][-+-+-+] [--++-+] [+---++] [-+--++] [+---++] [---+++]
… e quindi altri ancora…
K(4)= 34
K(5)= 89
K(6)= 233
K(7)= 610
K(8)= 1597
K(9)= 4181
K(10)= 10946
Una volta stabilite le K(n) la probabilità cercata si dovrebbe ottenere dalla formula…
P= p^2 *
[n=0,+00] K(n)*(p*q)^n (2)A questo punto [memore della cattiva strada intrapresa in precedenza…]mi fermerei un poco in attesa, se ve ne sono, di osservazioni da parte vostra…
cordiali saluti!…
lupo grigio
Modificato da - lupo grigio il 13/05/2004 11:22:28
Con una tabella a me sono venuti i seguenti valori probalistici in rapporto al numero di passi:
se in luogo del precipizio ci fosse stata una linea da superare:
La tabella al di sopra dei quattro passi diventa noiosissima da compilare e provando a calcolare le probablilità di caduta sopra questa soglia mi sono venuti risultati contraddittori, forse vale la pena perdere più tempo con la tabella...
Modificato da - cannigo il 13/05/2004 13:10:09
Passi Probabilità di caduta
0 0
1 0
2 1/9
3 1/25
4 5/73
se in luogo del precipizio ci fosse stata una linea da superare:
Passi Probabilità di trovarsi al di là della linea
2 1/9
3 1/27
4 9/81
La tabella al di sopra dei quattro passi diventa noiosissima da compilare e provando a calcolare le probablilità di caduta sopra questa soglia mi sono venuti risultati contraddittori, forse vale la pena perdere più tempo con la tabella...
Modificato da - cannigo il 13/05/2004 13:10:09
ho rifatto ancora i conti, stavolta mi viene 1/4.
a questo punto per una risposta definitiva mi rivolgo a tony che di queste cose mi sa che se ne intende
a questo punto per una risposta definitiva mi rivolgo a tony che di queste cose mi sa che se ne intende
Nell’ipotesi che l’impostazione da me data al problema sia corretta calcoliamo la probabilità P che ‘prima o poi’ l’ubriaco precipiti in finzione della probabilità p di avvicinarsi ad ogni passo al burrone. Per fare questo è sufficiente utilizzare la formula che qui riscriviamo…
P(p)= p^2 * [n=0,+00] K(n)*(p*q)^n (1)
… dove le K(n) sono debbono essere calcolate utilizzando la formula ricorsiva precedentemente descritta. La serie che compare nella (1) converge abbastanza rapidamente per tutti i valori di p e i risultati che seguono sono stati ottenuti sommando i primi cento termini di essa.
P(0)=0
P(.1)=.0123289527164
P(.2)=.0615835777126
P(.3)=.171697657571
P(.4)=.36018957346
P(.5)=.6
P(.6)=.810426540284
P(.7)=.934798357885
P(.8)=.985337243402
P(.9)=.998645170031
P(1)=1
Il risultato richiesto dal problema posto da cart [dove p=1/3] è P(.3333333…)=.225806451613. Se poniamo p=2/3 invece si ha P(.6666666…)=.903225806452. Sarebbe interessante appurare perché [sempre ammesso che i risultati da me forniti siano esatti…] nel caso di ‘passeggiata simmetrica’ [p=1/2] il risultato è ‘razionale’ e vale 3/5…
cordiali saluti!…
lupo grigio
P(p)= p^2 *
[n=0,+00] K(n)*(p*q)^n (1)… dove le K(n) sono debbono essere calcolate utilizzando la formula ricorsiva precedentemente descritta. La serie che compare nella (1) converge abbastanza rapidamente per tutti i valori di p e i risultati che seguono sono stati ottenuti sommando i primi cento termini di essa.
P(0)=0
P(.1)=.0123289527164
P(.2)=.0615835777126
P(.3)=.171697657571
P(.4)=.36018957346
P(.5)=.6
P(.6)=.810426540284
P(.7)=.934798357885
P(.8)=.985337243402
P(.9)=.998645170031
P(1)=1
Il risultato richiesto dal problema posto da cart [dove p=1/3] è P(.3333333…)=.225806451613. Se poniamo p=2/3 invece si ha P(.6666666…)=.903225806452. Sarebbe interessante appurare perché [sempre ammesso che i risultati da me forniti siano esatti…] nel caso di ‘passeggiata simmetrica’ [p=1/2] il risultato è ‘razionale’ e vale 3/5…
cordiali saluti!…
lupo grigio
scusami lupo grigio, ma ti ripeto che c'è qualcosa da rivedere.
conosci il problema detto "la rovina del giocatore?"
questo problema è identico.
il nostro ubriaco entra in un casinò con 2 euro.
gioca ad un gioco in cui se vince guadagna un euro e se perde ne perde uno.
calcolare la probabilità di rimanere prima o poi senza soldi.
è dimostrato (se vuoi posto la dimostrazione ma è lunghina...)
che se la probabilità di vincere è minore O UGUALE a quella di perdere, la probabilità di perdere tutto è 1.
se invece la prob è maggiore di vincere che di perdere bisogna fare qualche conto.
ti assicuro che questa non è una mia congettura ma un risultato dimostrato.
conosci il problema detto "la rovina del giocatore?"
questo problema è identico.
il nostro ubriaco entra in un casinò con 2 euro.
gioca ad un gioco in cui se vince guadagna un euro e se perde ne perde uno.
calcolare la probabilità di rimanere prima o poi senza soldi.
è dimostrato (se vuoi posto la dimostrazione ma è lunghina...)
che se la probabilità di vincere è minore O UGUALE a quella di perdere, la probabilità di perdere tutto è 1.
se invece la prob è maggiore di vincere che di perdere bisogna fare qualche conto.
ti assicuro che questa non è una mia congettura ma un risultato dimostrato.
Propongo un'altra strada ancora.Usiamo le notazioni che ormai si sono consolidate nel corso di questo topic.Vediamo k(n).Abbiamo n segni + ed n segni - da distribuire.Si potrebbe concludere dunque (2n,n),ma il risultato è ovviamente esagerato perchè non tutte le combinazioni sono buone.Quali dobbiamo scartare?Sicuramente le ++....ma anche le -+++..etc etc insomma tutte quelle per cui si abbia che la somma dei segni sia +2 ad un dato istante.La formula che propongo è:
k(n)=(2n,n)-(2n-2,n-2)-(2n-4,n-3)-...-(2,0).Infatti alla prima sottrazione stiamo dicendo che nelle combinazioni con ++ per essere completate rimangono n segni - ed n-2 segni + e queste sono in tutto (2n-2,n-2),analogamente per le altre..Per n=3 questo risultato prevede 15 in disaccordo con l'altra formula di lupo.In effetti ne ho trovate altre.Sviluppata quella somma di binomiali in funzione di n e sperando che il risulato non sia troppo brutto,si inserisce il tutto nella serie ed il gioco è fatto.
k(n)=(2n,n)-(2n-2,n-2)-(2n-4,n-3)-...-(2,0).Infatti alla prima sottrazione stiamo dicendo che nelle combinazioni con ++ per essere completate rimangono n segni - ed n-2 segni + e queste sono in tutto (2n-2,n-2),analogamente per le altre..Per n=3 questo risultato prevede 15 in disaccordo con l'altra formula di lupo.In effetti ne ho trovate altre.Sviluppata quella somma di binomiali in funzione di n e sperando che il risulato non sia troppo brutto,si inserisce il tutto nella serie ed il gioco è fatto.
Aggiornamento tabella:
Quando arrivo a dieci passi mi giro e sparo la cazzata
Passi Probabilità di caduta
1 0
2 1/9
3 1/25
4 5/73
5 5/213
6 25/617
Quando arrivo a dieci passi mi giro e sparo la cazzata
Ancora una volta l'osservazione di cart è 'quasi-esatta' e questo significa che il problema posto non è poi così elementare come si potrebbe intuire dal suo enunciato...
In effetti le K(3) non sono 13 come asserito da me e neppure 15 come asserito da cart... sono esattamente 14 e corrispondono alle seguenti...
[+-+-+-][+-+--+][+--++-][+--+-+][-+-++-][-+-+-+][-++-+-]
[-++--+][--+++-][--++-+][+---++][-+--++][--+-++][---+++]
In effetti esse si ottengono sottraendo dalle 6!/(3!*3!)=20 sequenze possibili di tre '+' e tre '-' le seqnenze 'non permesse'...
[+++---][++-+--][++--+-][++---+][+-++--][-+++--]
... che sono 6.
Come dice cart... occorre ripensarci un poco sù...
cordiali saluti!...
lupo grigio
In effetti le K(3) non sono 13 come asserito da me e neppure 15 come asserito da cart... sono esattamente 14 e corrispondono alle seguenti...
[+-+-+-][+-+--+][+--++-][+--+-+][-+-++-][-+-+-+][-++-+-]
[-++--+][--+++-][--++-+][+---++][-+--++][--+-++][---+++]
In effetti esse si ottengono sottraendo dalle 6!/(3!*3!)=20 sequenze possibili di tre '+' e tre '-' le seqnenze 'non permesse'...
[+++---][++-+--][++--+-][++---+][+-++--][-+++--]
... che sono 6.
Come dice cart... occorre ripensarci un poco sù...
cordiali saluti!...
lupo grigio
*quote:
Quando arrivo a dieci passi mi giro e sparo la cazzata [cannigo]
si trovi prima un padrino, signore!
ciao a tutti.
leggo in ritardo, e mi sento imbarazzato
la fiducia è ahimè mal riposta, perchè di queste cose io mi intendo assai poco.
comunque, per dimostrargli la mia riconoscenza,
VOTO PER MAVERICK
nel senso che appoggio la sua soluzione: P = 1/4
poi, per scaldare un po' il dibattito, azzardo un
è solo una mia congettura, ovviamente; sentiamo le reazioni.
tony
*Edited by - tony on 15/05/2004 06:46:15
leggo in ritardo, e mi sento imbarazzato
*quote:
ho rifatto ancora i conti, stavolta mi viene 1/4.
a questo punto per una risposta definitiva mi rivolgo a tony che di queste cose mi sa che se ne intende [Maverick]
la fiducia è ahimè mal riposta, perchè di queste cose io mi intendo assai poco.
comunque, per dimostrargli la mia riconoscenza,
VOTO PER MAVERICK
nel senso che appoggio la sua soluzione: P = 1/4
poi, per scaldare un po' il dibattito, azzardo un
p
P = (-----)^d
1 - p
con
P = probabil. di finire prima o poi nel burrone,
p = probabil. di fare il passo verso il burrone
d = distanza iniziale dal burrone, in passi
è solo una mia congettura, ovviamente; sentiamo le reazioni.
tony
*Edited by - tony on 15/05/2004 06:46:15
tony la formula usata da te è la stessa che ho usato io, dopo aver trovato la soluzione generale del sistema che avevo scritto con gli h
e imposto la minimalità della soluzione.
e imposto la minimalità della soluzione.
...e va beh, non avendo trovato il padrino mi accontento del 1/4
Correzione tabella:
PS
Non c'ho capito niente, secondo me esiste una probabilità massima di
1/9 al 2° passo
dopodichè la probabilità decresce fino ad arrivare a zero...
facendo una prova sperimentale il numero delle cadute non sarà mai un quarto dei passi effettuati...
Modificato da - cannigo il 17/05/2004 12:34:45
Passi Probabilità di caduta
2 1/9
4 4/72 + 1/9
6 20/612 + 4/72 + 1/9
PS
Non c'ho capito niente, secondo me esiste una probabilità massima di
1/9 al 2° passo
dopodichè la probabilità decresce fino ad arrivare a zero...
facendo una prova sperimentale il numero delle cadute non sarà mai un quarto dei passi effettuati...
Modificato da - cannigo il 17/05/2004 12:34:45
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo