SUPERCAT.DEV

Nell'articolo precedente abbiamo seguito un saldo che si muoveva di una unità alla volta:

+1
oppure
-1

La random walk poteva continuare senza una fine prestabilita.

Ora aggiungiamo due barriere.

Immaginiamo un capitale intero compreso fra:

$$ 0 e B $$

A ogni turno:

+1 con probabilità p
-1 con probabilità q = 1-p

Il processo termina appena il capitale raggiunge:

0   -> rovina
B   -> obiettivo raggiunto

La domanda è:

partendo da i, qual è la probabilità di arrivare a B prima di arrivare a 0?

Questo è il classico problema della rovina del giocatore.

Qui lo usiamo esclusivamente come modello probabilistico: non come strategia di puntata e non come promessa di profitto.

Un esempio concreto

stateDiagram-v2
    direction LR
    [*] --> Interno
    Interno --> Su: +1 con probabilità p
    Interno --> Giu: -1 con probabilità q
    Su --> Obiettivo: quando il capitale raggiunge B
    Giu --> Rovina: quando il capitale raggiunge 0
    Rovina --> Rovina
    Obiettivo --> Obiettivo

Le barriere 0 e B sono assorbenti: raggiungerne una termina la sessione.

Prendiamo:

$$ \begin{gathered} B = 10 \ i = 4 \end{gathered} $$

Partiamo quindi da un capitale 4.

Per raggiungere l'obiettivo dobbiamo arrivare a 10 prima di perdere tutto.

Se il gioco è equo:

$$ p = q = 1/2 $$

potremmo essere tentati di pensare:

probabilità di successo = 50%

Ma non è così.

La posizione iniziale non è a metà fra le due barriere:

distanza da 0  = 4
distanza da 10 = 6

Vediamo come calcolare la probabilità corretta.

Definiamo la probabilità a partire da ogni stato

Indichiamo con:

u_i

la probabilità di raggiungere B prima di 0 quando il capitale corrente è i.

Alle due barriere non c'è nulla da calcolare:

$$ \begin{gathered} u_0 = 0 \ u_B = 1 \end{gathered} $$

Se siamo invece in uno stato intermedio i, al turno successivo possiamo andare soltanto in:

i+1 con probabilità p
i-1 con probabilità q

Usando il teorema della probabilità totale, separiamo i due casi incompatibili ed esaustivi del prossimo passo: salire con probabilità p oppure scendere con probabilità q. In generale la regola è $P(B)=\sum_j P(B\mid A_j)P(A_j)$ quando gli $A_j$ formano tutti i casi possibili. Qui diventa:

u_i
=
p u_(i+1)
+
q u_(i-1)

Questa piccola equazione contiene l'intero problema.

Non stiamo chiedendo dove sarà la random walk dopo un numero fissato di passi.

Stiamo chiedendo quale delle due barriere verrà raggiunta per prima.

Caso equo: la probabilità è lineare

Se:

$$ p = q = 1/2 $$

la ricorrenza diventa:

u_i
=
(u_(i+1) + u_(i-1)) / 2

Moltiplicando per 2:

2u_i
=
u_(i+1)+u_(i-1)

quindi:

$$ u_{i+1}-u_i = u_i-u_{i-1} $$

Le differenze fra valori consecutivi sono costanti.

Perciò u_i deve essere una funzione lineare di i.

Con le condizioni:

$$ \begin{gathered} u_0 = 0 \ u_B = 1 \end{gathered} $$

otteniamo:

u_i
=
i/B

Questa è la formula della rovina del giocatore nel caso equo.

Il nostro caso: partire da 4 con obiettivo 10

Inseriamo:

$$ \begin{gathered} i = 4 \ B = 10 \end{gathered} $$

Otteniamo:

u_4
=
4/10
=
2/5
=
40%

La probabilità di rovina è quindi:

1 - 2/5
=
3/5
=
60%

Quindi un gioco può essere perfettamente equo a ogni singolo turno e avere comunque:

60%

di probabilità di raggiungere la barriera inferiore prima dell'obiettivo scelto.

Non c'è contraddizione.

Il valore atteso del prossimo passo è zero, ma la probabilità di raggiungere prima una barriera dipende anche da dove abbiamo iniziato.

Se partissimo da:

$$ \begin{gathered} i = 5 \ B = 10 \end{gathered} $$

allora nel caso equo avremmo davvero:

$$ u_5 = 1/2 $$

perché le due barriere sarebbero alla stessa distanza.

Se il gioco non è equo

Supponiamo ora:

$$ p \ne q $$

La ricorrenza resta:

u_i
=
p u_(i+1)
+
q u_(i-1)

Cerchiamo una soluzione della forma:

$$ u_i = z^i $$

Sostituendo:

$$ z^i = p z^{i+1} + q z^{i-1} $$

Dividendo per z^(i-1):

$$ p z^2 - z + q = 0 $$

Poiché:

$$ p+q=1 $$

le due radici sono:

1
q/p

La soluzione generale è quindi:

u_i
=
A
+
C (q/p)^i

Imponendo ancora:

$$ \begin{gathered} u_0=0 \ u_B=1 \end{gathered} $$

si ottiene:

u_i
=
[1-(q/p)^i]
/
[1-(q/p)^B]

per:

$$ p \ne q $$

Insieme al caso equo abbiamo quindi:

$$ \begin{gathered} p = q = 1/2: \ u_i = i/B \end{gathered} $$

p \ne q:

u_i
=
[1-(q/p)^i]
/
[1-(q/p)^B]

Basta un piccolo sbilanciamento per cambiare il risultato

Manteniamo:

$$ \begin{gathered} i = 4 \ B = 10 \end{gathered} $$

ma facciamo vincere il passo positivo soltanto con probabilità:

$$ \begin{gathered} p = 49% \ q = 51% \end{gathered} $$

Il valore atteso di un singolo passo è:

E[X]
=
(+1)0,49 + (-1)0,51
=
-0,02

Applicando la formula della rovina:

u_4
≈
35,2784%

La probabilità di rovina sale quindi a circa:

64,7216%

Per confronto, con le stesse barriere:

p = 49%  -> P(obiettivo prima di 0) ≈ 35,2784%
p = 50%  -> P(obiettivo prima di 0) = 40,0000%
p = 51%  -> P(obiettivo prima di 0) ≈ 44,8491%

La variazione di p sembra piccola.

Ma viene applicata ripetutamente lungo una traiettoria che può durare molti passi.

Valore atteso e probabilità di rovina sono domande diverse

Questo articolo completa un punto già emerso negli articoli sul valore atteso e sulle progressioni di puntata.

Il valore atteso del singolo passo ci dice:

quanto guadagniamo o perdiamo in media per turno

La probabilità di rovina ci chiede invece:

quale barriera viene raggiunta per prima

Sono grandezze diverse.

Nel caso equo:

$$ E[X]=0 $$

ma partendo da 4 con barriere 0 e 10:

P(rovina)=60%

Questo non significa che il gioco abbia valore atteso negativo.

Significa soltanto che, con quelle barriere e quello stato iniziale, la barriera inferiore è più vicina.

Analogamente, una progressione di puntata non può essere giudicata soltanto dalla frequenza con cui produce una piccola vincita: bisogna distinguere valore atteso, capitale necessario, distribuzione finale e rischio di raggiungere una barriera finanziaria.

Il processo termina davvero?

Nel modello finito:

$$ 0,1,...,B $$

con passi +1/-1 e probabilità fisse, il processo raggiunge infine una delle due barriere con probabilità 1.

Quindi:

P(raggiunge B prima di 0)
+
P(raggiunge 0 prima di B)
=
1

Non resta una terza probabilità positiva associata a una traiettoria che vaga per sempre fra 1 e B-1.

Per questo possiamo parlare senza ambiguità di probabilità di successo e probabilità di rovina come eventi complementari.

Verifica C#: formula e sistema di equazioni

Lo standalone C# associato a questo articolo è:

RovinaGiocatore.cs

Possiamo controllare il risultato in due modi indipendenti.

Il primo usa direttamente la formula chiusa.

Il secondo costruisce le equazioni:

$$ u_i - p u_{i+1} - q u_{i-1} = 0 $$

per tutti gli stati interni e risolve il sistema lineare.

Uno schema essenziale è:

static double ProbabilitaFormula(
    int capitale,
    int obiettivo,
    double p)
{
    if (obiettivo <= 0)
        throw new ArgumentOutOfRangeException(nameof(obiettivo));

    if (capitale < 0 || capitale > obiettivo)
        throw new ArgumentOutOfRangeException(nameof(capitale));

    if (p < 0.0 || p > 1.0)
        throw new ArgumentOutOfRangeException(nameof(p));

    if (capitale == 0)
        return 0.0;

    if (capitale == obiettivo)
        return 1.0;

    if (p == 0.0)
        return 0.0;

    if (p == 1.0)
        return 1.0;

    double q = 1.0 - p;

    if (Math.Abs(p - q) < 1e-15)
        return capitale / (double)obiettivo;

    double r = q / p;

    return
        (1.0 - Math.Pow(r, capitale))
        /
        (1.0 - Math.Pow(r, obiettivo));
}

Nel file standalone associato all'articolo il caso p=49/100 viene calcolato anche come frazione esatta con BigInteger, poi confrontato con la soluzione del sistema lineare e con una simulazione a seed fisso.

La simulazione resta una verifica empirica.

La risposta matematica viene dalla ricorrenza e dalle condizioni alle barriere.

Che cosa non abbiamo ancora calcolato

Abbiamo risposto a:

quale barriera verrà raggiunta per prima?

Non abbiamo ancora risposto a:

quando verrà raggiunta?

Il numero di passi necessari è una nuova variabile casuale.

E c'è una domanda ancora più importante:

possiamo decidere di fermarci usando ciò che abbiamo osservato fino a quel momento senza utilizzare informazioni future?

Questa è precisamente l'idea che introduce i tempi di arresto, argomento del prossimo articolo.

Il punto da ricordare

La rovina del giocatore trasforma la random walk dell'articolo precedente in un problema di primo raggiungimento di una barriera.

Nel caso equo:

P_i(raggiungere B prima di 0)
=
i/B

Nel caso sbilanciato:

P_i
=
[1-(q/p)^i]
/
[1-(q/p)^B]

La lezione più importante non è una strategia di gioco.

È una distinzione probabilistica:

un processo può avere incrementi medi nulli e tuttavia avere una probabilità di rovina molto diversa dal 50%, perché il risultato dipende dallo stato iniziale e dalle barriere che abbiamo imposto.