Sequenze

[Piera]

Ripropongo il seguente quesito.
Si consideri una successione di lanci di una moneta con P(Testa)=p.
Calcolare la probabilità che una sequenza di x teste, cioè x teste consecutive, esca prima di una sequenza di y croci.

[enomis_costa88]

Questo problema mi interessava perchè avevo trovato (a meno di granchi) una soluzione ricorsiva ma mi ero un po' incasinato poi non l'ho più trovato sul forum..

Sia chiamata ” $ (t,x,y) $ buona” ogni sequenza creata come segue:
Inizio a tirare, al primo lancio esce una testa.
Smetto di tirare appena ottengo una stringa di esattamente x teste consecutive oppure una stringa di esattamente y croci consecutive.

Sia chiamata ” $ (c,x,y) $ buona” ogni sequenza creata come segue:
Inizio a tirare, al primo lancio esce una croce.
Smetto di tirare appena ottengo una stringa di esattamente x teste consecutive oppure una stringa di esattamente y croci consecutive.

Sia chiamata “ $ (x,y) $ buona” ogni sequenza che è o $ (c,x,y) $ buona o $ (t,x,y) $ buona.

Sia $ A(c,x,y) $ la probabilità che una sequenza “ $ (x,y) $ buona” sia ” $ (c,x,y) $ buona” e termini con una testa.

Sia $ A(t,x,y) $ la probabilità che una sequenza “ $ (x,y) $ buona” sia ” $ (t,x,y) $ buona” e termini con una testa.

Ottengo facilmente:
$ A(t,1,y) = p $

La possibilità che una sequenza “(1,y) buona” termini con una croce è pari alla possibilità di non avere teste nei primi y lanci ovvero:

$ 1-(A(t,1,y) + A(c,1,y)) = (1-p)^y $ da cui ottengo :
$ A(c,1,y) = 1-(1-p)^y - p $.

Ogni sequenza:
"(x,y) buona"
terminante con una testa
contenente i stringhe di almeno x-1 teste consecutive (l’ultima sequenza di x teste consecutive è contata solo una volta)
è formata come segue (se i>1):

Inizia con una sequenza "(x-1,y) buona" terminante con testa.
Poi è seguita da i-2 distinte sequenze "(c,x-1,y) buone" terminanti con testa.
Infine c’è una sequenza (c,x-1,y) buona terminante con testa seguita da una testa.

Se i=1 allora è formata come segue:

Inizia con una sequenza "(x-1,y) buona" terminanti con testa, è seguita poi da un’altra testa.

Ricavo quindi facilmente le seguenti relazioni ricorsive:

$ A(c,x,y)=\sum_{i=1}^{\infty}A(c,x-1,y)^{i}*p $
$ A(t,x,y)= \sum_{i=1}^{\infty}A(t,x-1,y)*A(c,x-1,y)^{i-1}*p $

La probabilità cercata è equivalente a :
$ A(c,x,y)+A(t,x,y) $

EDIT: coretto un refuso.