SUPERCAT.DEV

Nell'articolo precedente abbiamo continuato a lanciare un dado finché non è comparso il terzo 6.

La probabilità di successo restava sempre:

$$ 1/6 $$

perché ogni lancio era indipendente dagli altri.

Ora cambiamo esperimento.

Mescoliamo un mazzo standard da 52 carte e iniziamo a pescarle senza reinserimento.

La domanda è:

Quante carte dobbiamo osservare prima di vedere il secondo re?

A prima vista sembra ancora un problema di tempo di attesa.

Lo è.

Ma non possiamo usare la binomiale negativa.

Dopo ogni carta estratta il mazzo cambia e, con esso, cambia anche la probabilità che la carta successiva sia un re.

Questa è la situazione descritta dalla distribuzione ipergeometrica inversa.

Stessa domanda, modello diverso

Mettiamo a confronto gli ultimi due articoli.

Nella binomiale negativa:

fisso il numero di successi da raggiungere
→ continuo le prove finché li ottengo
→ p resta costante

Nell'ipergeometrica inversa:

fisso il numero di successi da raggiungere
→ estraggo senza reinserimento da una popolazione finita
→ la composizione residua cambia
→ p non resta costante

Il contrasto è lo stesso già incontrato fra:

binomiale

e:

ipergeometrica

ma ora la domanda è invertita: non fissiamo quante carte estrarre; fissiamo quanti successi vogliamo osservare.

Fissiamo la notazione

Useremo:

K = successi totali nella popolazione
B = insuccessi totali
N = K + B = dimensione totale della popolazione
k = numero di successi che vogliamo raggiungere
X = posizione alla quale compare il k-esimo successo

Nel mazzo, se consideriamo successo = re:

K = 4 re
B = 48 non-re
N = 52 carte
k = 2

Quindi:

X = posizione del secondo re nel mazzo mescolato

Quali valori può assumere X?

Il secondo re può arrivare immediatamente:

K♠ K♥

quindi il minimo è:

$$ X = 2 $$

Qual è invece il massimo?

Possiamo osservare prima tutti i:

48 non-re

poi un re e infine il secondo re.

Quindi:

X massimo = 48 + 2 = 50

Il supporto è dunque finito:

$$ X = 2,3,4,...,50 $$

Questa è già una differenza importante rispetto alla binomiale negativa, il cui tempo di attesa non possiede un massimo finito.

In generale:

$$ X = k, k+1, ..., B+k $$

Il modo più pulito di contare: scegliamo le posizioni dei successi

Dopo aver mescolato il mazzo, le quattro posizioni occupate dai re formano un sottoinsieme di quattro posizioni fra le 52 disponibili.

Tutti i sottoinsiemi di quattro posizioni sono equiprobabili.

Il loro numero è:

$$ \binom{52}{4} $$

Questo ci permette di calcolare direttamente la probabilità che il secondo re si trovi esattamente in una posizione x.

Per avere:

$$ X = x $$

serve che:

nelle prime x-1 posizioni ci sia esattamente 1 re
la posizione x sia un re
nelle posizioni successive ci siano gli altri 2 re

La posizione x è già fissata.

Dobbiamo quindi scegliere:

1 posizione da re fra le prime x-1

in:

$$ \binom{x-1}{1} $$

modi, e:

2 posizioni da re fra le 52-x successive

in:

$$ \binom{52-x}{2} $$

modi.

Quindi:

P(X=x)
=
C(x-1,1) · C(52-x,2)
----------------------
       C(52,4)

per:

$$ x = 2,...,50 $$

La formula generale

Con:

K successi totali
B insuccessi totali
N = K+B
k successi da raggiungere

per avere il k-esimo successo esattamente alla posizione x dobbiamo:

scegliere k-1 successi nelle prime x-1 posizioni
fissare un successo alla posizione x
collocare gli altri K-k successi dopo x

I casi favorevoli sono quindi:

$$ \binom{x-1}{k-1} \cdot \binom{N-x}{K-k} $$

mentre le possibili posizioni dei K successi nella popolazione sono:

$$ \binom{N}{K} $$

Otteniamo:

P(X=x)
=
C(x-1,k-1) · C(N-x,K-k)
--------------------------------
             C(N,K)

per:

$$ x = k,...,B+k $$

Questa è la funzione di massa dell'ipergeometrica inversa nella convenzione usata in questo articolo.

Perché si chiama "inversa"?

L'ipergeometrica ordinaria, introdotta nell'articolo 09, chiede:

fisso il numero di estrazioni m
→ quanti successi trovo?

L'ipergeometrica inversa chiede:

fisso il numero di successi k
→ quante estrazioni servono?

La parola inversa riguarda quindi il modo in cui formuliamo la domanda.

Non significa che stiamo calcolando una funzione inversa in senso algebrico.

Secondo re esattamente alla ventesima carta

Mettiamo:

$$ x = 20 $$

nella formula.

Dobbiamo scegliere:

1 re nelle prime 19 posizioni

e:

2 re nelle 32 posizioni successive alla ventesima

Quindi:

P(X=20)
=
C(19,1) · C(32,2)
-------------------
      C(52,4)

Il rapporto si riduce a:

$$ 9424 / 270725 $$

cioè circa:

3,481023%

Non è la probabilità che la ventesima carta sia un re.

È una domanda più specifica:

la ventesima carta deve essere precisamente il secondo re osservato.

Un controllo immediato con l'articolo 08

Consideriamo il valore minimo:

$$ X = 2 $$

Significa che i primi due risultati sono entrambi re.

La formula dell'ipergeometrica inversa dà:

P(X=2)
=
C(1,1) · C(50,2)
-----------------
     C(52,4)
=
1/221

Nell'articolo 08 avevamo calcolato direttamente:

$$ 4/52 \cdot 3/51 = 1/221 $$

Le due strade coincidono esattamente.

È un buon controllo: una nuova distribuzione non deve contraddire i casi particolari già risolti con probabilità condizionata.

Entro la ventesima carta: torniamo all'ipergeometrica

Ora chiediamo:

Qual è la probabilità di aver già visto il secondo re entro la ventesima carta?

Nel linguaggio del tempo di attesa:

$$ P(X \le 20) $$

Ma dire che il secondo re è già comparso entro 20 carte significa esattamente che nelle prime 20 carte abbiamo osservato:

almeno 2 re

Se chiamiamo Y il numero di re nelle prime 20 carte:

Y ~ Ipergeometrica(N=52,K=4,m=20)

allora:

$$ P(X \le 20) = P(Y \ge 2) $$

Il risultato esatto è:

$$ 27113 / 54145 $$

cioè circa:

50,074799%

Quindi la ventesima carta è anche la mediana minima del tempo di attesa del secondo re:

$$ \begin{gathered} P(X \le 19) < 50% \ P(X \le 20) > 50% \end{gathered} $$

La stessa simmetria vista nell'articolo 29

Nel caso con probabilità costante avevamo:

binomiale negativa:
P(X <= n)
=
P(Binomiale(n,p) >= r)

Ora abbiamo l'analogo senza reinserimento:

ipergeometrica inversa:
P(X <= m)
=
P(Ipergeometrica(N,K,m) >= k)

È una relazione importante.

Le distribuzioni "inverse" non descrivono un mondo separato: riformulano come tempo di attesa lo stesso processo che le distribuzioni ordinarie descrivono come numero di successi in un campione fissato.

Il valore atteso: dove cade in media il k-esimo successo?

Per l'ipergeometrica inversa vale:

$$ E[X] = k(N+1)/(K+1) $$

Nel nostro caso:

E[X]
=
2·53/5
=
106/5
=
21,2

Quindi il secondo re compare mediamente attorno alla posizione:

21,2

Questo valore può essere capito senza sviluppare una lunga somma della PMF.

Immaginiamo le K posizioni dei successi ordinate nel mazzo.

Esse dividono i B insuccessi in:

K+1

spazi:

prima del primo successo
fra primo e secondo
...
dopo l'ultimo successo

Per simmetria, ogni spazio contiene in media:

$$ B/(K+1) $$

insuccessi.

Prima del k-esimo successo ci sono k di questi spazi, quindi in media:

kB/(K+1)

insuccessi.

Aggiungendo i k successi stessi:

E[X]
=
k + kB/(K+1)

Poiché:

$$ N=K+B $$

otteniamo:

$$ E[X] = k(N+1)/(K+1) $$

Anche la varianza ha una forma chiusa

Per questa convenzione:

Var(X)
=
k · B · (N+1) · (K-k+1)
--------------------------------
 (K+2) · (K+1)^2

Per il secondo re:

Var(X)
=
2544/25
=
101,76

quindi:

sigma
=
sqrt(2544/25)
≈
10,087616

La posizione del secondo re è quindi molto dispersa: il valore medio 21,2 non implica affatto che il secondo re compaia quasi sempre vicino alla carta 21.

Un confronto con il reinserimento

Supponiamo, per confronto, di estrarre una carta, rimetterla nel mazzo e mescolare ogni volta.

La probabilità di re rimarrebbe costante:

$$ p = 4/52 = 1/13 $$

Il tempo fino al secondo re seguirebbe allora una binomiale negativa con:

$$ \begin{gathered} r = 2 \ p = 1/13 \end{gathered} $$

Il valore atteso sarebbe:

E[X]
=
2/(1/13)
=
26

Senza reinserimento abbiamo invece:

E[X]
=
21,2

Non possiamo quindi sostituire automaticamente una popolazione finita con prove indipendenti a probabilità costante.

Il meccanismo di campionamento fa parte del modello.

Il primo re non segue una geometrica

Anche con:

$$ k=1 $$

l'ipergeometrica inversa non diventa una geometrica.

Per il primo re:

E[X]
=
53/5
=
10,6

Se fingessimo invece che ogni estrazione fosse indipendente con:

$$ p=1/13 $$

la geometrica avrebbe media:

13

La differenza nasce dal fatto che, quando estraiamo una non-re senza reinserirla, la frazione di re nel mazzo residuo aumenta.

La distribuzione deve sommare a 1

Il supporto del secondo re è finito:

2,...,50

Questi eventi sono incompatibili e coprono tutte le possibilità.

Quindi deve valere:

$$ \sum (x=2..50) P(X=x) = 1 $$

Questa è una verifica numerica molto utile dell'implementazione.

A differenza della binomiale negativa, non dobbiamo troncare una coda infinita: possiamo sommare tutta la distribuzione.

Il calcolo in C#

Lo standalone C# associato a questo articolo è:

IpergeometricaInversa.cs

La formula si traduce direttamente con BigInteger per i conteggi combinatori.

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 IpergeometricaInversa(
    int posizione,
    int successiTotali,
    int insuccessiTotali,
    int successiRichiesti)
{
    if (successiTotali <= 0)
        throw new ArgumentOutOfRangeException(
            nameof(successiTotali));

    if (insuccessiTotali < 0)
        throw new ArgumentOutOfRangeException(
            nameof(insuccessiTotali));

    if (successiRichiesti <= 0 ||
        successiRichiesti > successiTotali)
    {
        throw new ArgumentOutOfRangeException(
            nameof(successiRichiesti));
    }

    int popolazione =
        successiTotali + insuccessiTotali;

    if (posizione < successiRichiesti ||
        posizione > insuccessiTotali + successiRichiesti)
    {
        return 0.0;
    }

    BigInteger favorevoli =
        Combinazioni(
            posizione - 1,
            successiRichiesti - 1)
        *
        Combinazioni(
            popolazione - posizione,
            successiTotali - successiRichiesti);

    BigInteger totali =
        Combinazioni(
            popolazione,
            successiTotali);

    return (double)favorevoli / (double)totali;
}

Per il secondo re alla carta 20:

double p = IpergeometricaInversa(
    posizione: 20,
    successiTotali: 4,
    insuccessiTotali: 48,
    successiRichiesti: 2);

Console.WriteLine($"{p:P9}");

otteniamo circa:

3,481023179%

Il file standalone associato all'articolo aggiunge:

• normalizzazione sull'intero supporto 2..50;
• confronto esatto della CDF (cumulative distribution function), cioè $F(x)=P(X\le x)$, con la coda ipergeometrica;
• media e varianza teoriche;
• simulazione senza reinserimento con seed fisso;
• gate sui casi X=2 e X<=20.

Le ipotesi del modello contano

L'ipergeometrica inversa richiede una popolazione finita con:

K successi
B insuccessi

campionata:

senza reinserimento

fino al raggiungimento del successo numero k.

Non è il modello giusto se:

• rimettiamo l'elemento dopo ogni estrazione;
• la popolazione viene modificata da meccanismi diversi dalla semplice rimozione;
• la probabilità di successo cambia per ragioni esterne non rappresentate dalla composizione residua.

In questi casi serve un altro modello.

Il punto pratico

Dopo gli articoli 09, 29 e 30 possiamo vedere una struttura comune.

ipergeometrica:
fisso quante estrazioni faccio
→ conto quanti successi ottengo

ipergeometrica inversa:
fisso quanti successi voglio
→ conto quante estrazioni servono

La funzione di massa è:

P(X=x)
=
C(x-1,k-1) C(N-x,K-k)
------------------------
         C(N,K)

con:

$$ x = k,...,B+k $$

Nel mazzo standard, per il secondo re:

$$ \begin{gathered} E[X] = 21,2 \ P(X=20) \approx 3,481023% \ P(X\le 20) \approx 50,074799% \end{gathered} $$

Il passaggio fondamentale è sempre lo stesso: prima di scegliere una formula dobbiamo chiedere come viene campionata la popolazione.

Nel prossimo articolo abbandoneremo i tempi di attesa e torneremo a un problema storico che ha contribuito alla nascita stessa della probabilità moderna: come dividere equamente il premio quando una partita viene interrotta prima della fine.