Il problema del carro armato tedesco

C'era un mio amico che voleva avviare una piccola azienda in proprio. Si era organizzato per tutta la burocrazia (suppongo poca, essendo lui l'unico titolare e dipendente) e, una volta pronto per lavorare, aveva fatto mettere un po' di pubblicità sulla sua auto, sulla quale aveva anche appiccicato un piccolo adesivo con un numero: 2.

Perché 2, gli domandai. Perché, mi rispose, se metto 1 sembro un poveraccio, se metto 2 vuol dire che ho una azienda bene avviata con almeno due auto, e magari anche qualcuna di più, vai a sapere.

Niente da dire, di fronte al genio ci si può solo inchinare.

Mi è venuta in mente questa storiella dopo aver letto l'ultimo what if di xkcd, quello in cui si cerca di dare una risposta alla domanda seguente: quanto sarebbero lunghe le nostre timeline di twitter se si potessero estendere lungo lo schermo in entrambe le direzioni?

In un futuro più o meno remoto, dice Randall Munroe, tutti gli account che seguiamo su twitter smetteranno di scrivere. Questo è abbastanza ovvio, (anche se account come quello del Big Ben potrebbero andare avanti per tanto); stabilire quando succederà, però, non è facile.

In inglese questo tipo di stima viene chiamato German Tank Problem, perché è un problema che si è presentato realmente durante la seconda guerra mondiale quando si è trattato di organizzare lo sbarco in Normandia: gli alleati, avendo notato la presenza del carro armato Panther negli eserciti tedeschi, si preoccuparono un po', perché erano sicuri che i loro Sherman si sarebbero comportati bene in eventuali scontri con carri tedeschi di vecchia generazione, ma questi Panther sembravano un po' troppo veloci e potenti.

Insomma, quanti Panther hanno questi tedeschi?, si domandarono i generali alleati.

Ah, saperlo!, fu la risposta un po' troppo evasiva.

Al che si decise di risolvere il problema seguendo due strade: lo spionaggio e la matematica. Sullo spionaggio c'è poco da dire, funziona più o meno in questo modo: trova qualcuno che sappia e usa qualunque mezzo per ottenere l'informazione. Sulla matematica invece diciamo qualcosa di più.

Alcuni pezzi con i quali venivano costruiti i Panther avevano dei numeri di serie: il cambio, il telaio, il motore e le ruote. Numeri di serie progressivi, come le auto fittizie del mio amico.

E quindi, ecco il problema: abbiamo catturato il Panther numero 60: quanti ce ne sono ancora in giro?

Citando xkcd, diciamo che la risposta ha a che fare con il problema di statistica più discusso su internet: usiamo l'approccio frequentista o bayesiano? In ogni caso, come ragioniamo?

Una prima, facile, considerazione: ci sono almeno 60 carri armati: la probabilità che il numero dei carri sia un valore compreso tra 0 e 59 è nulla.

Andiamo avanti: supponiamo che esistano N carri; la probabilità di incontrare il numero 60 è naturalmente di 1/N (ovviamente questa è la probabilità di incontrare un certo carro, non importa quale sia il suo numero di serie), se N è maggiore di 60, altrimenti la probabilità è zero. Quindi la probabilità massima la abbiamo quando N = 60.

Naturalmente non abbiamo la certezza che il numero sia proprio quello (come ci dice anche l'intuizione). Come possiamo fare una stima migliore? Sarebbe opportuno vedere qualche altro carro.

Facciamo un esempio numerico, per poi arrivare alla formula. Supponiamo che ci siano N = 200 carri, e supponiamo di averne visti 3. Supponiamo anche di essere stati fortunati, e di aver trovato 3 numeri di serie equidistanti tra di loro: 50, 100 e 150. Se il primo numero fosse 0, avremmo quindi questa situazione:

Se dunque m è il massimo numero di serie che abbiamo trovato (150) e k è il numero di carri ispezionati (3), possiamo stimare il valore di N calcolando la distanza m/k tra un numero di serie e il successivo (150/3 = 50) e sommandola a m.

In realtà, però, se vogliamo contare i carri armati non possiamo partire da 0: immaginiamo che il primo numero di serie sia 1. Per mantenere la simmetria nella suddivisione in k parti uguali, supponiamo allora che l'ultimo termine sia N+1. Insomma, invece di fare i conti sull'intervallo 1,…, N li facciamo sull'intervallo 0,…, N+1. La formula che abbiamo trovato sopra per stimare il valore di N stima, in realtà, N+1. Dunque sottraiamo 1 e siamo a posto. Il risultato è questo:

N = m + m/k - 1.

Se, quindi, abbiamo catturato 5 carri, e il numero di serie maggiore che abbiamo visto è 60, la stima che facciamo sul totale è N = 60 + 60/5 - 1 = 71.

Ho fatto una simulazione per verificare il tutto: ho imposto N = 200, poi ho cominciato a estrarre numeri casuali (cioè numeri di serie di carri) da 1 a 200, e ho calcolato il valore presunto di N man mano che il numero di carri aumentava. Ecco qua:

Si vede che, quando capita un numero fortunato, la stima migliora notevolmente, e verso i 50 carri è ormai indistinguibile dal valore reale (50 su 200 sono tanti, sì, ma anche con numeri notevolmente inferiori si possono avere stime molto buone: se devi sbarcare in Normandia un conto è sapere che ci sarà un qualche centinaio di carri, un altro è sapere che ce ne saranno a migliaia).

Questo è quello che fanno i frequentisti. I bayesiani, invece, ragionano in modo diverso (dopo aver litigato un po' con i frequentisti). Quando trovano il primo carro armato fanno una prima stima del numero totale dei carri; più precisamente, assegnano un valore di probabilità a tutti i numeri da 1 a un certo valore massimo sufficientemente alto. Ogni volta che trovano un nuovo carro ricalcolano tutta la distribuzione di probabilità, tenendo conto delle nuove informazioni.

Ecco un grafico (i conti no, non li metto, sono complicati, però si può dare un'occhiata qua, a pagina 102, dove viene segnalato anche un programma che fa tutto da solo, programma che ho leggermente modificato per produrre il grafico qua sotto):

Va letto in questo modo: la curva viola (quella più a sinistra) è la stima del numero massimo di carri fatta utilizzando un solo numero di serie. Le curve più a destra sono state ottenute aggiungendo nuovi numeri di serie, fino a 10. Si vede che la distribuzione di probabilità diventa più stretta e più alta, cioè più precisa.

Ecco come si presenta la distribuzione dopo 20 estrazioni:

Un'ultima considerazione prima di concludere: come ha funzionato l'altro metodo, quello dello spionaggio, nella realtà?

Bé, dopo la guerra molte informazioni segrete sono diventate pubbliche, tra cui anche il numero di carri prodotti nei vari mesi della guerra. Per esempio, nel giugno 1940 l'analisi statistica ha stimato una produzione di 169 unità, mentre lo spionaggio pensava che ne venissero costruiti 1000. Il dato reale era 122. L'anno dopo, nel giugno 1941, la statistica fornì una stima di 244 carri, contrapposta al dato fornito dallo spionaggio di 1550 unità. Il dato reale fu 271. Infine, nell'agosto del 1942 la statistica stimò una produzione di 327 carri, le spie invece una produzione di 1550, e il dato reale era 342.

Credo che ci sia una morale, in questo.