SUPERCAT.DEV

Due giocatori, A e B, disputano una partita composta da manche indipendenti.

Vince il premio chi arriva per primo a:

4 vittorie

La partita viene però interrotta quando il punteggio è:

$$ \begin{gathered} A = 2 \ B = 1 \end{gathered} $$

Il premio totale, che sarebbe andato interamente al vincitore, è:

160 €

Non possiamo più completare la partita.

La domanda è:

Come dividiamo equamente i 160 € tenendo conto della situazione raggiunta?

Questo è il classico problema delle parti, o problem of the points: uno dei problemi storici che contribuirono alla nascita del calcolo delle probabilità.

La risposta non dipende da quanto i due giocatori hanno già “guadagnato” in senso morale. Dipende dal valore probabilistico della posizione corrente.

Un po' di storia, senza trasformarla nel problema

Il problema è più antico della celebre corrispondenza fra Pascal e Fermat, ma è proprio il confronto del 1654 fra i due matematici, sollecitato dal Chevalier de Méré, ad averlo reso un episodio fondamentale della storia della probabilità.

La domanda storica era sostanzialmente la stessa:

una partita viene interrotta prima che qualcuno raggiunga il numero di vittorie previsto
→
come dividere la posta in modo equo?

Qui useremo il problema soprattutto per la sua idea matematica:

valore della posizione corrente
=
probabilità di vincere da questo momento in poi

Prima di calcolare: fissiamo il modello

Assumiamo che ogni manche futura sia:

indipendente dalle precedenti

con:

P(A vince una manche) = 1/2
P(B vince una manche) = 1/2

Dal punteggio:

$$ \begin{gathered} A = 2 \ B = 1 \end{gathered} $$

per arrivare a 4 vittorie:

A deve ancora vincere 2 manche
B deve ancora vincere 3 manche

Indichiamo quindi:

n = 2  vittorie ancora necessarie ad A
m = 3  vittorie ancora necessarie a B

La storia precedente della partita è ormai conosciuta.

Con manche future indipendenti e con probabilità costante, per valutare il premio ci interessa soltanto lo stato corrente:

A necessita di 2 vittorie
B necessita di 3 vittorie

Perché non basta dividere secondo il punteggio?

Una prima idea potrebbe essere:

A ha 2 vittorie
B ha 1 vittoria

quindi dividiamo il premio:

2/3 ad A
1/3 a B

Su 160 € significherebbe circa:

$$ \begin{gathered} A = 106,67 ,\text{€} \ B = 53,33 ,\text{€} \end{gathered} $$

Ma il punteggio già ottenuto non misura direttamente la probabilità di vincere la partita.

Il regolamento dice:

vince chi arriva per primo a 4

Dal punto attuale A deve vincere soltanto 2 manche, mentre B ne deve vincere 3.

La domanda corretta è quindi:

Qual è la probabilità che A ottenga 2 vittorie prima che B ne ottenga 3?

Primo metodo: completiamo virtualmente tutte le manche possibili

Da questo stato la partita reale può durare al massimo:

n + m - 1
=
2 + 3 - 1
=
4 manche

Perché non può arrivare a una quinta manche?

Dopo quattro risultati futuri abbiamo distribuito in totale quattro vittorie fra A e B.

Se A non ne ha ottenute almeno 2, allora ne ha ottenute al massimo 1 e B ne ha ottenute almeno 3: B avrebbe già vinto.

Possiamo quindi usare un trucco molto potente:

immaginiamo di giocare comunque quattro manche virtuali, anche se nella realtà la partita terminerebbe prima.

Le manche dopo la conclusione reale non cambiano chi avrebbe vinto.

A vince la partita se, nelle quattro manche virtuali, ottiene almeno:

2 vittorie

Contiamo le 16 continuazioni

Con quattro manche eque e indipendenti esistono:

2^4
=
16

sequenze equiprobabili.

A vince se ottiene:

2, 3 oppure 4 vittorie

Le sequenze favorevoli sono:

C(4,2) + C(4,3) + C(4,4)
=
6 + 4 + 1
=
11

Quindi:

P(A vince)
=
11/16
=
68,75%

Per B resta:

P(B vince)
=
5/16
=
31,25%

Questa è già la divisione probabilisticamente equa della posta.

Dividiamo i 160 €

Il valore corrente della posizione di A è:

160 · 11/16
=
110 €

quello di B è:

160 · 5/16
=
50 €

Quindi la divisione equa è:

$$ \begin{gathered} A = 110 ,\text{€} \ B = 50 ,\text{€} \end{gathered} $$

Non perché A abbia “meritato” 110 €.

Ma perché, se potessimo ripetere moltissime volte una partita da quello stesso stato, A incasserebbe il premio finale circa nel 68,75% dei casi.

La formula generale con la binomiale

Supponiamo che da un certo stato:

A debba ancora vincere n manche
B debba ancora vincere m manche

Ogni manche è indipendente e A la vince con probabilità:

$$ p $$

mentre:

$$ q = 1-p $$

Il massimo numero di manche ancora rilevanti è:

$$ r = n + m - 1 $$

Se immaginiamo di disputarle tutte virtualmente, A vince la partita se ottiene almeno n vittorie fra queste r manche.

Quindi:

P(A vince)
=
sum da k=n a r
C(r,k) p^k q^(r-k)

È una coda binomiale.

Nel nostro caso:

$$ \begin{gathered} n = 2 \ m = 3 \ r = 4 \ p = 1/2 \end{gathered} $$

perciò:

P(A vince)
=
C(4,2)/16
+
C(4,3)/16
+
C(4,4)/16
=
11/16

Secondo metodo: fermiamoci davvero quando A raggiunge la seconda vittoria

Possiamo risolvere lo stesso problema senza immaginare manche giocate dopo la fine.

A può vincere:

alla seconda manche futura
alla terza manche futura
alla quarta manche futura

A vince in 2 manche

Deve vincere entrambe:

AA

Probabilità:

$$ (1/2)^2 = 1/4 $$

A vince in 3 manche

L'ultima deve essere vinta da A.

Nelle prime due deve esserci esattamente:

1 vittoria di A
1 vittoria di B

Ci sono:

$$ \binom{2}{1}=2 $$

possibilità:

ABA
BAA

Probabilità totale:

$$ 2/8 = 1/4 $$

A vince in 4 manche

L'ultima deve ancora essere di A.

Nelle prime tre A deve aver vinto una volta e B due volte:

C(3,2)
=
3

sequenze.

Probabilità:

$$ 3/16 $$

Sommiamo eventi disgiunti:

P(A vince)
=
1/4 + 1/4 + 3/16
=
4/16 + 4/16 + 3/16
=
11/16

Stesso risultato.

Il collegamento con la binomiale negativa

L'articolo 29 chiedeva:

quante prove servono per raggiungere il successo numero r?

Qui possiamo leggere una vittoria di A come “successo”.

A vince il match se il suo secondo successo arriva prima che B abbia accumulato tre successi propri.

La formula generale può quindi essere scritta anche come:

P(A vince)
=
sum da i=0 a m-1
C(n+i-1,i)
p^n q^i

Il termine con indice i descrive il caso in cui, quando A ottiene la sua n-esima vittoria, B ne ha ottenute esattamente i.

Per:

$$ \begin{gathered} n=2 \ m=3 \ p=1/2 \end{gathered} $$

abbiamo:

i=0 -> C(1,0)/2^2 = 1/4
i=1 -> C(2,1)/2^3 = 2/8
i=2 -> C(3,2)/2^4 = 3/16

ancora:

$$ 11/16 $$

Quindi il problema delle parti collega direttamente:

coda binomiale
↔
tempo fino all'n-esimo successo

Terzo metodo: ragioniamo ricorsivamente sul prossimo punto

Chiamiamo:

$$ W(n,m) $$

la probabilità che A vinca quando ad A servono ancora n vittorie e a B ne servono m.

Alla prossima manche possono accadere soltanto due cose.

Con probabilità p, vince A e lo stato diventa:

$$ (n-1,m) $$

Con probabilità 1-p, vince B e lo stato diventa:

$$ (n,m-1) $$

Quindi:

$$ W(n,m) = p W(n-1,m) + (1-p) W(n,m-1) $$

con condizioni al bordo:

$$ W(0,m)=1 $$

perché A ha già raggiunto il proprio obiettivo, e:

$$ W(n,0)=0 $$

perché B ha già raggiunto il suo.

Per il nostro caso equo:

W(2,3)
=
1/2 W(1,3)
+
1/2 W(2,2)

Per simmetria:

$$ W(2,2)=1/2 $$

Inoltre, se ad A serve una sola vittoria e a B ne servono tre, A perde soltanto se B vince tre volte di fila:

W(1,3)
=
1-(1/2)^3
=
7/8

Quindi:

W(2,3)
=
1/2 · 7/8
+
1/2 · 1/2
=
7/16 + 4/16
=
11/16

Tre percorsi diversi, stesso valore.

Se A è più forte, il punteggio da solo dice ancora meno

Finora abbiamo assunto:

$$ p=1/2 $$

Supponiamo invece che A vinca ogni manche con probabilità:

$$ p=0,6 $$

Restano sempre:

$$ \begin{gathered} n=2 \ m=3 \ r=4 \end{gathered} $$

La probabilità di A diventa:

P(A vince)
=
C(4,2)0,6^2 0,4^2
+
C(4,3)0,6^3 0,4
+
C(4,4)0,6^4

cioè:

513/625
=
82,08%

Il punteggio è identico:

2-1

ma il valore della posizione è molto diverso.

Per dividere equamente un premio dobbiamo quindi conoscere anche il modello delle manche future, non soltanto il tabellone.

Un esempio che mostra quanto possa essere fuorviante il rapporto dei punti

Immaginiamo una partita al primo che arriva a 5, interrotta sul:

$$ \begin{gathered} A = 4 \ B = 2 \end{gathered} $$

Con giocatori equivalenti, ad A basta ancora una vittoria mentre B ne deve ottenere tre.

A perde soltanto se B vince le prossime tre manche:

P(A perde)
=
(1/2)^3
=
1/8

quindi:

P(A vince)
=
7/8
=
87,5%

Il rapporto del punteggio direbbe invece:

4/(4+2)
=
2/3
≈
66,67%

Sono due quantità completamente diverse.

Il calcolo in C#

Lo standalone C# associato a questo articolo è:

ProblemaDelleParti.cs

Possiamo implementare sia la coda binomiale sia la ricorrenza.

using System.Numerics;

static BigInteger Combinazioni(int n, int k)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    if (k < 0 || k > n)
        return BigInteger.Zero;

    k = Math.Min(k, n - k);

    BigInteger risultato = BigInteger.One;

    for (int i = 1; i <= k; i++)
    {
        risultato *= n - k + i;
        risultato /= i;
    }

    return risultato;
}

static double ProbabilitaABinomiale(
    int vittorieMancantiA,
    int vittorieMancantiB,
    double probabilitaA)
{
    if (vittorieMancantiA <= 0 ||
        vittorieMancantiB <= 0)
    {
        throw new ArgumentOutOfRangeException();
    }

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

    int manche =
        vittorieMancantiA + vittorieMancantiB - 1;

    double somma = 0.0;

    for (int k = vittorieMancantiA;
         k <= manche;
         k++)
    {
        somma +=
            (double)Combinazioni(manche, k)
            * Math.Pow(probabilitaA, k)
            * Math.Pow(1.0 - probabilitaA, manche - k);
    }

    return somma;
}

Per il nostro stato:

double pA = ProbabilitaABinomiale(
    vittorieMancantiA: 2,
    vittorieMancantiB: 3,
    probabilitaA: 0.5);

Console.WriteLine($"{pA:P4}");

otteniamo:

68,7500%

Il file standalone associato all'articolo aggiunge:

• enumerazione completa delle 2^(n+m-1) continuazioni per casi piccoli;
• coda binomiale;
• ricorrenza con memoizzazione;
• conteggio esatto 11/16 nel caso equo;
• divisione del premio 110 € / 50 €;
• gate anche per p=0,6 e per il caso 4-2 al primo che arriva a 5.

Che cosa significa davvero “divisione equa”?

La divisione:

premio totale · probabilità residua di vittoria

è equa rispetto al modello probabilistico dichiarato.

Se le manche non sono indipendenti, se la forza dei giocatori cambia, se esistono pareggi, vantaggio di servizio, ordine di gioco o altre informazioni rilevanti, allora lo stato deve contenere più dati.

Non possiamo usare 11/16 fuori dal modello che lo ha prodotto.

Il principio invece resta valido:

valore equo della posizione
=
valore atteso del premio futuro

Il punto pratico

Il problema delle parti mostra una distinzione fondamentale:

punteggio già osservato
!=
probabilità di vittoria residua

Per una partita interrotta dobbiamo partire dallo stato corrente e chiedere:

quali continuazioni future sono ancora possibili?
con quali probabilità?
chi vince in ciascuna continuazione?

Nel nostro esempio:

A necessita 2 vittorie
B necessita 3 vittorie
p=1/2

quindi:

P(A vince)=11/16=68,75%
P(B vince)= 5/16=31,25%

Per un premio da 160 €:

$$ \begin{gathered} A = 110 ,\text{€} \ B = 50 ,\text{€} \end{gathered} $$

Il risultato può essere ottenuto con:

continuazioni virtuali
coda binomiale
binomiale negativa
ricorrenza sul prossimo punto

Questa equivalenza è più importante del singolo numero: ci mostra che lo stesso problema probabilistico può essere guardato come conteggio, distribuzione o equazione ricorsiva.

Nel prossimo articolo useremo proprio una distribuzione di tempo di attesa già incontrata per affrontare un altro classico: il problema delle due scatole di fiammiferi di Banach.