SUPERCAT.DEV

Immaginiamo di avere due scatole di fiammiferi:

sinistra: N fiammiferi
destra:   N fiammiferi

Ogni volta che serve un fiammifero scegliamo una delle due tasche completamente a caso:

P(sinistra) = 1/2
P(destra)   = 1/2

Se la scatola scelta contiene ancora almeno un fiammifero, ne prendiamo uno.

Prima o poi, però, scegliamo una tasca e scopriamo che la scatola è già vuota.

In quell'istante ci fermiamo e chiediamo:

Quanti fiammiferi sono rimasti nell'altra scatola?

Questo è il classico problema delle scatole di fiammiferi di Banach.

La domanda sembra un semplice esercizio di conteggio, ma contiene una sottigliezza importante: il momento in cui una scatola diventa vuota non coincide necessariamente con quello in cui ci accorgiamo che è vuota.

Svuotare una scatola non significa ancora scoprirla vuota

Supponiamo che la scatola destra contenga inizialmente:

$$ N = 10 $$

Dopo averla scelta dieci volte con successo, abbiamo tolto il suo ultimo fiammifero.

Da quel momento la scatola destra è vuota.

Ma il processo non termina ancora.

Potremmo continuare a scegliere la scatola sinistra per diverse richieste senza accorgerci di nulla.

La scatola destra viene scoperta vuota soltanto quando la scegliamo di nuovo.

Quindi il processo ha due momenti distinti:

ultimo fiammifero tolto
        ↓
scatola fisicamente vuota
        ↓
possibili scelte dell'altra scatola
        ↓
nuova scelta della scatola vuota
        ↓
scoperta del vuoto e arresto

È proprio quest'ultima scelta, quella fallita, che dobbiamo includere nel modello.

La variabile che vogliamo studiare

Chiamiamo:

K = numero di fiammiferi rimasti
    nell'altra scatola
    quando scopriamo la prima scatola vuota

Dato che entrambe le scatole partono con N fiammiferi:

$$ K = 0,1,2,...,N $$

Tutti questi valori sono possibili.

Per esempio:

$$ K = N $$

significa che, prima della scoperta, abbiamo consumato tutti i fiammiferi di una scatola senza usare mai l'altra.

Invece:

$$ K = 0 $$

significa che al momento della prima scoperta entrambe le scatole sono già state completamente consumate.

Condizioniamo sulla scatola che scopriamo vuota

Per costruire il conteggio supponiamo, per il momento, che la prima scatola scoperta vuota sia quella destra.

Se nell'altra scatola restano k fiammiferi, dalla sinistra ne abbiamo già usati:

$$ N-k $$

Chiamiamo:

$$ x = N-k $$

il numero di scelte riuscite della scatola sinistra prima dell'arresto.

Per poter scoprire la destra vuota dobbiamo invece averla scelta con successo esattamente:

N volte

per consumarne tutti i fiammiferi, e poi dobbiamo sceglierla una volta ancora.

La situazione è quindi:

prima della scelta finale:
N scelte riuscite a destra
x scelte riuscite a sinistra

scelta finale:
destra di nuovo -> scatola vuota -> stop

Quante sequenze possono precedere la scelta finale?

Prima del tentativo fallito abbiamo effettuato:

$$ N+x $$

scelte riuscite.

Fra queste devono esserci:

N scelte a destra
x scelte a sinistra

Il loro ordine può essere qualsiasi.

Il numero di sequenze è quindi:

$$ \binom{N+x}{N} $$

Ogni sequenza completa, includendo la scelta finale a destra, ha probabilità:

$$ (1/2)^{N+x+1} $$

Perciò:

P(K=k e destra scoperta vuota per prima)
=
C(N+x,N) / 2^(N+x+1)

con:

$$ x=N-k $$

La simmetria raddoppia il risultato

La stessa identica situazione può verificarsi scambiando sinistra e destra.

Quindi moltiplichiamo per 2:

$$ P(K=k) = 2 \cdot \binom{N+x}{N} / 2^{N+x+1} $$

ossia:

$$ P(K=k) = \binom{N+x}{N} / 2^{N+x} $$

Sostituendo:

$$ x=N-k $$

otteniamo la formula finale:

$$ \begin{gathered} \binom{2N-k}{N} \ P(K=k) = ------------------------- \ 2^{2N-k} \ k=0,1,...,N \end{gathered} $$

Questa è la distribuzione esatta del numero di fiammiferi rimasti nell'altra scatola al momento della scoperta.

Il collegamento con la binomiale negativa

L'articolo 29 ha studiato la domanda:

quante prove servono per raggiungere il successo numero r?

Qui, condizionando sulla scoperta della scatola destra vuota, possiamo chiamare:

successo = scelta della tasca destra
insuccesso = scelta della tasca sinistra

La scoperta del vuoto avviene alla:

(N+1)-esima scelta della destra

perché le prime N hanno consumato i N fiammiferi e la successiva scopre che non ne resta nessuno.

Il numero x=N-k di scelte della sinistra prima di quel momento ha quindi esattamente la struttura della binomiale negativa.

C'è però una condizione ulteriore importante:

$$ x \le N $$

Se scegliessimo la sinistra più di N volte prima della scoperta a destra, avremmo già scoperto vuota la scatola sinistra e il processo sarebbe terminato dall'altra parte.

Quindi stiamo usando una massa della binomiale negativa all'interno del processo di arresto reale delle due scatole.

Esempio completo: dieci fiammiferi per scatola

Poniamo:

$$ N=10 $$

Allora:

$$ P(K=k) = \binom{20-k}{10} / 2^{20-k} $$

La distribuzione è:

k rimasti   Probabilità
0           17,619705%
1           17,619705%
2           16,692352%
3           14,837646%
4           12,219238%
5            9,164429%
6            6,109619%
7            3,491211%
8            1,611328%
9            0,537109%
10           0,097656%

Una prima sorpresa è:

$$ \begin{gathered} P(K=0)=P(K=1) \ \approx 17,62% \end{gathered} $$

mentre lasciare completamente intatta l'altra scatola è molto raro:

$$ P(K=10) = 1/1024 \approx 0,097656% $$

La distribuzione deve sommare a 1

Un controllo essenziale è:

$$ \sum (k=0..N) P(K=k) = 1 $$

Per N=10 possiamo verificarlo senza arrotondamenti scegliendo il denominatore comune:

$$ 2^{20} $$

Infatti:

$$ P(K=k) = \binom{20-k}{10}\cdot 2^k / 2^{20} $$

quindi deve valere l'identità:

Σ(k=0..10) C(20-k,10)·2^k
=
2^20
=
1.048.576

Il controllo esatto torna.

Quanti fiammiferi restano in media?

Ora che conosciamo tutta la distribuzione possiamo calcolare il valore atteso direttamente:

$$ E[K] = \sum (k=0..N) k P(K=k) $$

Per N=10:

E[K]
=
707825 / 262144
≈
2,700138

Quindi dieci fiammiferi per scatola non significano che, quando scopriamo il primo vuoto, l'altra ne contenga tipicamente ancora cinque.

Il meccanismo di arresto favorisce situazioni in cui entrambe le scatole sono già abbastanza consumate.

La mediana, per N=10, è addirittura:

2

perché:

P(K<=2)
≈
51,9318%

Un caso minuscolo che possiamo controllare a mano

Con:

$$ N=1 $$

abbiamo soltanto:

K=0 oppure K=1

La formula dà:

$$ P(K=0) = \binom{2}{1}/2^2 = 1/2 $$

mentre:

$$ P(K=1) = \binom{1}{1}/2^1 = 1/2 $$

Quindi:

$$ E[K]=1/2 $$

che possiamo verificare immediatamente anche enumerando le prime scelte possibili.

Con N=2 otteniamo invece:

$$ \begin{gathered} P(K=0)=3/8 \ P(K=1)=3/8 \ P(K=2)=1/4 \end{gathered} $$

con:

$$ E[K]=7/8 $$

Questi casi piccoli sono ottimi gate per il programma.

Verifica con C#

Lo standalone C# associato a questo articolo è:

FiammiferiBanach.cs

Per la formula esatta conviene usare BigInteger.

Il file standalone associato all'articolo:

FiammiferiBanach.cs

esegue tre controlli diversi:

1. calcola la PMF esatta;
2. verifica con interi che la massa totale sia 1;
3. simula il processo con seed fisso e confronta le frequenze.

Il cuore del calcolo è:

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

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

    return
        Combinazioni(2 * n - k, n)
        * BigInteger.Pow(2, k);
}

Tutte le masse vengono espresse sul denominatore comune:

$$ 2^{2N} $$

così la normalizzazione non dipende da confronti fra double.

Perché questo problema è importante

Il problema di Banach mette insieme diverse idee già incontrate:

combinazioni
+
prove sequenziali
+
binomiale negativa
+
regola di arresto
+
distribuzione di una quantità osservata allo stop

Ma soprattutto mostra che dobbiamo definire con precisione quando osserviamo il sistema.

La domanda:

quanti fiammiferi restano quando una scatola diventa vuota?

non è la stessa domanda di:

quanti fiammiferi restano quando scopriamo che una scatola è vuota?

Cambiare il momento di osservazione cambia la variabile casuale e quindi cambia la distribuzione.

Questa idea sarà ancora più importante nel prossimo articolo.

Prossimo passo

Finora l'istante di osservazione era determinato dal processo stesso:

ci fermiamo quando scopriamo una scatola vuota

Nel prossimo articolo cambieremo prospettiva.

Immagineremo di arrivare come osservatori in un istante casuale e chiederemo quale intervallo abbiamo più probabilità di intercettare.

Scopriremo un effetto controintuitivo:

gli intervalli lunghi vengono osservati più spesso proprio perché sono lunghi.

È il paradosso dell'ispezione.