Quiz

[panurgo]

Dal blog di Tanya Khovanova

Alice e Bob lanciano un dado "onesto" a sei facce finché non ottengono due risultati consecutivi uguali. Quindi sommano tutti i valori ottenuti: se il totale è pari vince Alice, se è dispari vince Bob. Chi ha maggiori probabilità di vittoria?

[franco]

A occhio direi che le probabilità di vittoria di Alice sono 7/12.

[panurgo]

Sei un poco esagerato...

[Alessandro B]

Alice vince 4 volte su 7

Bob vince 3 volte su 7

[franco]

Il ragionamento che avevo fatto (evidentemente sbagliato) era che Alice vince sicuramente se il gioco termina dopo soli due lanci in quanto la somma è evidentemente pari.
Se il gioco dura di più, pari e dispari sono equiprobabili.
Quindi, in 1/6 dei casi (secondo dado uguale al primo) vince Alice; i casi restanti (5/6) si dividono 5/12 a Alice e 5/12 a Bob.
Da cui il 7/12 per Alice che avevo detto.

Probabilmente ho fatto qualche errore stupido
Comunque sono curioso di conoscere il ragionamento corretto!

[Alessandro B]

Ciao Franco,
il tuo ragionamento sarebbe corretto se il gioco finisse sempre entro il terzo lancio.

Ma il gioco può durare anche più di 3 lanci...

[franco]

Hai ragione.
Avevo pensato che, ad esempio con 4 lanci, le possibili combinazioni dei primi 2 avessero somma equiprobabile, pari o dispari.
Invece devo escludere i casi in cui formavano una coppia di numeri uguali. Quindi c'è una lieve prevalenza di dispari.

[panurgo]

Alessandro, $4/7$ sono un filino scarsi...

[panurgo]

Chi ha maggiori probabilità di vittoria?

La domanda non è: qual è la probabilità di vittoria di Alice e Bob: basta un ragionamento che dimostri che Alice è favorita.

[Gianfranco]

Ci provo, sapendo che la probabilità è piena di tranelli...

a) Due numeri uguali non cambiano la parità della somma precedente alla loro uscita.
b) All'inizio del gioco la parità della somma (= 0) è certamente pari, mentre dopo ogni lancio successivo è 50% pari, 50% dispari.
c) Se ai primi due lanci escono due numeri uguali, vince sicuramente Alice.
d) Nei lanci successivi, invece, la probabilità sembra uguale per Alice e per Bob.
e) Il vantaggio iniziale aumenta la probabilità di Alice di vincere.

[panurgo]

Corretto, anche se noto la tua prudenza quando scrivi "sembra". In qualunque momento del processo il processo stesso è caratterizzato dall'ultimo numero uscito e dal totale ottenuto sino ad allora. E in qualunque momento del processo (escluso l'inizio) entrambi, ultimo risultato e totale, possono essere pari o dispari quindi abbiamo quattro possibilità (le lettere minuscole per l'ultimo risultato, le maiuscole per la somma): $\text{pP}$, $\text{dD}$, $\text{pD}$ e $\text{dP}$.

AlexRyba.20.png (11.27 KiB) Visto 28491 volte

In figura sono illustrati i possibili esiti del tiro successivo a secondo dello stato in cui ci si trova: in ogni caso uno dei possibili esiti porta alla fine del gioco vuoi in $\text{P}$, somma finale pari, vuoi in $\text{D}$, somma finale dispari.

Per esempio, se siamo in $\text{pP}$, uno dei tre esiti pari porta in $\text{P}$, gli altri due portano in $\text{pP}$ mentre i tre esiti dispari portano in $\text{dD}$. Lo stesso vale, mutatis mutandis, per gli altri tre stati.

Mettendo bene insieme il tutto in un diagramma otteniamo (in figura, a sinistra)

AlexRyba.21.png (15.4 KiB) Visto 28491 volte

Nella parte destra della figura troviamo il diagramma ottenuto scambiando tra di loro $\text{P}$ e $\text{D}$: osserviamo che il secondo diagramma è uguale al primo ruotato di $180^\circ$, cioè il processo è simmetrico rispetto al suddetto scambio.
Ciò che non è simmetrico è il primo tiro: la parità dell'esito e della somma non sono tra loro indipendenti (la somma è uguale all'esito) quindi solo due degli stati attivi sono accessibili

AlexRyba.22.png (13.41 KiB) Visto 28491 volte

quelli che portano in una mossa in $\text{P}$. La parte successiva del processo è simmetrica come abbiamo visto quindi Alice è favorita.

[Gianfranco]

Grazie Guido, fenomenale, come sempre!
Per calcolare la probabilità di Alice avevo fatto lo stesso ragionamento di Franco:
p(Alice) = 7/12 = 0,58333...
Ma facendo una simulazione, mi è venuto:
p(Alice) = 0,57...
Dal tuo grafo è possibile ricavare le probabilità di Alice e di Bob?

[franco]

Il mio ragionamento in realtà non era corretto in quanto le opzioni "pari/dispari" prima dei due tiri uguali che chiudono la partita non sono identiche.
Faccio un esempio giusto per chiarezza.
Immaginiamo che la partita si sia chiusa con una coppia di 6 al terzo e quarto lancio.
Fra tutte le 36 combinazioni possibili dei precedenti due lanci devo escluderne 11 (quelle che non mi avrebbero consentito di arrivare appunto al quarto lancio):
1-6 2-6 3-6 4-6 5-6 6-6 1-1 2-2 3-3 4-4 5-5
Le 25 combinazioni "valide" rimanenti sono 15 dispari e 10 pari.
(Se la partita si fosse chiusa con una coppia di 5, sempre al quarto lancio, avrei dovuto escludere 1-5 2-5 3-5 4-5 5-5 6-5 1-1 2-2 3-3 4-4 6-6 ... non cambia nulla)

[Gianfranco]

Franco, sapevo che era sbagliata ma ho voluto unirmi per solidarietà.
Mal comune mezzo gaudio.
Comunque non è propriamente sbagliata, si può considerare un'approssimazione di primo livello.

[panurgo]

Dal tuo grafo è possibile ricavare le probabilità di Alice e di Bob?

Il gioco è un Processo Markoviano: le probabilità di transizione da uno stato all'altro non dipendono dalla storia del processo.

Modifico il diagramma per esplicitare che gli stati $\text{P}$ e $\text{D}$ sono stati assorbenti: una volta arrivati tutti i tiri successivi non cambiano il risultato (sei esiti su sei portano allo stesso stato)

AlexRyba.30.png (11.46 KiB) Visto 28461 volte

Raccogliamo le probabilità di transizione in una matrice: la matrice di transizione

$T=\frac16\pmatrix{
6 & 1 & 1 & 0 & 0 & 0 \\
0 & 2 & 0 & 3 & 0 & 0 \\
0 & 3 & 0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 & 3 & 0 \\
0 & 0 & 3 & 0 & 2 & 0 \\
0 & 0 & 0 & 1 & 1 & 6 }$

e le probabilità di essere in ciascuno stato dopo il primo passo in un vettore

$y_1=\frac16\pmatrix{
0 \\
3 \\
3 \\
0 \\
0 \\
0 }$

Per un processo di Markov, $y_r$ (il vettore delle probabilità dopo $r$ passi) si ottiene applicando la matrice di transizione al vettore $y_{r-1}$: ad esempio

$y_2=T\cdot y_1=\frac16\pmatrix{
6 & 1 & 1 & 0 & 0 & 0 \\
0 & 2 & 0 & 3 & 0 & 0 \\
0 & 3 & 0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 & 3 & 0 \\
0 & 0 & 3 & 0 & 2 & 0 \\
0 & 0 & 0 & 1 & 1 & 6 }\cdot\frac16\pmatrix{
0 \\
3 \\
3 \\
0 \\
0 \\
0 }=\frac1{36}\pmatrix{
6 \\
6 \\
9 \\
6 \\
9 \\
0 }$

Evidentemente sarà $y_r=T^{r-1}\cdot y_1$ quindi dobbiamo calcolare la potenza della matrice $T$.

La potenza di una matrice diagonale è uguale alla matrice diagonale delle potenze degli elementi diagonali: es.

$\pmatrix{1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2}^2=\pmatrix{1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2}\cdot\pmatrix{1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2}=\pmatrix{1 & 0 & 0 \\ 0 & 9 & 0 \\ 0 & 0 & 4}$

quindi se $T$ è una matrice diagonalizzabile allora

$T=S\cdot\Lambda\cdot S^{-1}=S\cdot\text{diag}\left\{\lambda_k\right\}\cdot S^{-1}$

(dove $\lambda_k$ sonoo gli autovalori della matrice $T$) e infine

$T^{r-1}=S\cdot\text{diag}\left\{\lambda_k^{r-1}\right\}\cdot S^{-1}$

Ora calcoliamo il limite

$T^\infty=\lim\limits_{r\to\infty}{T^{r-1}}=S\cdot\text{diag}\left\{\lim\limits_{r\to\infty}{\lambda_k^{r-1}}\right\}\cdot S^{-1}$

e otteniamo la matrice di transizione dopo infiniti passi. Il vettore

$y_\infty=T^\infty\cdot y_1$

contiene le probabilità cercate.

Ovviamente non mi sogno neanche di fare tutta quest'algebra a mano: scrivo

Codice: Seleziona tutto

{{6,1,1,0,0,0},{0,2,0,3,0,0},{0,3,0,2,0,0},{0,0,2,0,3,0},{0,0,3,0,2,0},{0,0,0,1,1,6}}/6

su WolframAlpha e fra le tante cose che ricavo trovo anche la

AlexRyba.40.png (50.48 KiB) Visto 28461 volte

Abbiamo

$\lim\limits_{n\to\infty}{\left(-\frac16\right)^n}=\lim\limits_{n\to\infty}{\left(\frac56\right)^n}=\lim\limits_{n\to\infty}{\left(-\frac{\sqrt5i}6\right)^n}=\lim\limits_{n\to\infty}{\left(\frac{\sqrt5i}6\right)^n}=0$

quindi

$\Lambda^\infty=\pmatrix{0&&&&&\\&0&&&&\\&&1&&&\\&&&1&&\\&&&&0&\\&&&&&0}$

con

$T^\infty=S\cdot \Lambda^\infty\cdot S^{-1}=\frac1{41}\pmatrix{41&26&21&20&15&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&15&20&21&26&41}$

e

$y_\infty=\frac1{41}\pmatrix{41&26&21&20&15&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&0&0&0&0&0\\
0&15&20&21&26&41}\cdot \frac16\pmatrix{0\\3\\3\\0\\0\\0}=\pmatrix{\frac{47}{82}\\0\\0\\0\\0\\\frac{35}{82}}$