Esercizio - Rovina del giocatore alla roulette - probabilità di vittoria e durata attesa

Teoria: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafiPasseggiata sulla retta con barriere (rovina del giocatore): da i con N come traguardo, P(vittoria)=i/N e durata attesa i(N-i) se il gioco è equo; con p diverso da 1/2, P=(1-r^i)/(1-r^N), r=q/p. Il 2-SAT si risolve con una passeggiata randomizzata (flip di una variabile di una clausola violata): E[T] ≤ n^2 passi, quindi 2n^2 passi bastano con errore ≤ 1/2 (3-SAT: deriva contraria, esponenziale). Sul grafo la passeggiata ha π_v=d(v)/2m, tempo di ritorno 2m/d(v), tempo di copertura < 4m(n-1), da cui la connettività s-t in spazio logaritmico; PageRank è la stazionaria di una passeggiata con teletrasporto.Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi →.

Testo. Un giocatore parte con $10$ euro e punta $1$ euro a partita. Si ferma quando arriva a $20$ euro o a $0$.

1. Gioco equo ($p=\tfrac12$): probabilità di arrivare a $20$ e numero medio di partite.
2. Roulette americana (38 caselle, 18 rosse), puntando sempre sul rosso: $p=\tfrac{18}{38}=\tfrac9{19}$. Stesse domande.
3. Con la stessa roulette, un secondo giocatore parte da $90$ euro e vuole arrivare a $100$; un terzo parte da $10$ e vuole arrivare a $100$. Probabilità di successo e durata.
4. Nel gioco equo, dimostrare $P_i=i/N$ con un argomento alternativo (valore atteso del capitale) e controllare che sia coerente con la formula.
5. Verificare con una simulazione.

Soluzione

1. Gioco equo, $N=20$, $i=10$: $P_{10}=\tfrac{10}{20}=\boxed{\tfrac12}$ e $D_{10}=10\cdot(20-10)=\boxed{100}$ partite.

2. $q=\tfrac{10}{19}$, quindi $r=\tfrac qp=\tfrac{10/19}{9/19}=\tfrac{10}9$, $q-p=\tfrac1{19}$. $$P_{10}=\frac{1-r^{10}}{1-r^{20}}=\frac{1}{1+r^{10}}=\frac1{1+(10/9)^{10}}=\frac1{1+2{,}8680}=\boxed{0{,}2585}.$$ (la semplificazione: $1-r^{20}=(1-r^{10})(1+r^{10})$.) La durata è $D_{10}=\dfrac{i-NP_i}{q-p}=19\,(10-20\cdot0{,}2585)=19\cdot4{,}829=\boxed{91{,}76}$ partite. Con lo stesso capitale e lo stesso traguardo, un vantaggio della banca di soli $5{,}3$ punti percentuali per partita ($q-p=\tfrac1{19}$) fa scendere la probabilità di vittoria da $50\%$ a circa $26\%$.

3. Giocatore da $90$ a $100$ ($N=100$, $i=90$): $r^{90}=13\,127{,}3$ e $r^{100}=37\,648{,}6$, quindi $P_{90}=\dfrac{1-r^{90}}{1-r^{100}}=\dfrac{13\,126{,}3}{37\,647{,}6}=0{,}3487$, e $D_{90}=19\,(90-100\cdot0{,}3487)=19\cdot55{,}13=1047{,}5$ partite. Giocatore da $10$ a $100$: $r^{10}=2{,}868$, $P_{10}=\dfrac{r^{10}-1}{r^{100}-1}=\dfrac{1{,}868}{37\,647{,}6}=4{,}96\cdot10^{-5}$ e $D_{10}=19\,(10-100\cdot4{,}96\cdot10^{-5})=189{,}9$ partite: quasi sempre si perde tutto in circa $190$ partite. Con $p\ne\tfrac12$ la probabilità di vittoria dipende in modo esponenziale dalla distanza dal traguardo: per $N-i$ grande vale circa $r^{-(N-i)}\,(1-r^{-i})$.

4. Sia $X_n$ il capitale dopo $n$ partite nel gioco equo: $E[X_{n+1}\mid X_n]=X_n+\tfrac12(+1)+\tfrac12(-1)=X_n$, quindi $E[X_n]=i$ per ogni $n$ finché il gioco continua. Il gioco termina quasi certamente in tempo finito $T$ con $E[T]<\infty$ (la durata $D_i$ è finita), e il capitale è limitato in $[0,N]$; si può quindi passare al limite, $E[X_T]=i$ (teorema di arresto per martingale limitate). Ma $X_T\in\{0,N\}$, quindi $E[X_T]=N\,P_i$ e $P_i=i/N$ ✓. Per $p\ne\tfrac12$ la quantità conservata è $(q/p)^{X_n}$: $E[r^{X_{n+1}}\mid X_n]=r^{X_n}(p\,r^{+1}+q\,r^{-1})=r^{X_n}(q+p)=r^{X_n}$ perché $r=q/p$; con $E[r^{X_T}]=r^i$ si ottiene $r^i=P_ir^N+(1-P_i)$, cioè $P_i=\frac{1-r^i}{1-r^N}$ ✓ (la stessa formula).

5. Simulazione (seme fisso).

import random
rng = random.Random(1)

def parti(i, N, p):
    t = 0
    while 0 < i < N:
        i += 1 if rng.random() < p else -1
        t += 1
    return i == N, t

def formula(i, N, p):
    if p == 0.5: return i / N, i * (N - i)
    r = (1 - p) / p
    P = (1 - r**i) / (1 - r**N)
    return P, (i - N * P) / (1 - 2 * p)

for (i, N, p) in [(10, 20, 0.5), (10, 20, 9 / 19), (90, 100, 9 / 19), (10, 100, 9 / 19)]:
    T = 40000 if N <= 20 else 5000
    ris = [parti(i, N, p) for _ in range(T)]
    vit = sum(v for v, _ in ris) / T
    dur = sum(t for _, t in ris) / T
    print((i, N), "formula", [round(x, 4) for x in formula(i, N, p)], " simulazione", round(vit, 4), round(dur, 1))

Output tipico (varia con il seme; l'ultimo caso ha probabilità troppo piccola per essere vista in $5000$ prove, ma la durata sì):

(10, 20) formula [0.5, 100] simulazione ~0.50 ~100
(10, 20) formula [0.2585, 91.757] simulazione ~0.26 ~91.7
(90, 100) formula [0.3487, 1047.5438] simulazione ~0.35 ~1047
(10, 100) formula [0.0, 189.9057] simulazione 0.0 ~190