venerdì 4 ottobre 2013

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 = 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 = 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 = 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.

19 commenti:

Lucio ha detto...

Clap clap! Ottimo post!
Se posso permettermi, mancano due cose:
la stima degli errori e il confronto delle previsioni frequentiste-bayesiane.
L'accordo stima statistica - numero di carri armati vero sarebbe ancora più sensazionale con gli errori statistici, e sarebbe bello vedere come la guerra frequentista-bayesiana sia quasi puramente una questione di principio, dato che i risultati sono spesso molto simili (non so se questo è il caso, comunque).

zar ha detto...

Eh, mi sa che non ne so abbastanza sulla stima degli errori per fare un post senza errori :-) Qualcuno però potrebbe ampliare il discorso...




Juhan ha detto...

Adesso te la dovrai vedere con tutti gli statistici. E l'NSA (quella continua come al solito).

.mau. ha detto...

ecco perché non riuscivo a capirlo! Cercavo di fare i conti con l'approccio bayesiano! (per me in questi casi finiti i risultati devono essere gli stessi)

zar ha detto...

Dici il post di xkcd?

.mau. ha detto...

no, il problema del carro armato (è da anni che lo conosco)

Anonimo ha detto...

La morale è che i numeri seriali delle armi non dovrebbero essere in serie (emmm..) per non dare informazioni al nemico. Il numero seriale infatti dovrebbe dare indicazione sul suo lotto di produzione e oggi con un db non c'è nessuna ragione per numerare i pezzi da 1 a n.

L'altra morale è che la matematica funziona molto meglio dello spionaggio. :-)

zar ha detto...

Eh, sì, bisognerebbe criptarli in un qualche modo...

agapetòs ha detto...

Mi (vi) pongo tre domande.
#1. Il grafico dell'approccio frequentista ha discontinuità per N=5, N=17 e N=38. Qual è il motivo? Qual è la legge generale?
#2. Nell'approccio Bayesiano che distribuzione si assume a priori? uniforme?
#3. Un problema per certi versi simile è di questo tipo: c'è un ballottaggio tra due candidati. Al 50% dello scrutinio il candidato A ha il 60% dei voti, il candidato B ha il 40% dei voti. Qual è la la probabilità che il candidato A vinca il ballottaggio? Quale sarebbe l'approccio frequentista in questo caso?

.mau. ha detto...

per la 1, immagino che le discontinuità arrivino con l'arrivo di numeri grandi.

zar ha detto...

Sì, i salti sono assolutamente casuali, e corrispondono all'uscita di un numero fortunato, cioè alto. La legge generale è quella scritta nel testo: N=m+m/k-1. Ogni volta che m (il massimo numero trovato) si aggiorna, si nota un salto.

Credo che (.mau., sei tu quello che sa di robe bayesiane) nell'approccio bayesiano si parta sempre da 1/N, e poi si adatti la distribuzione in base ai numeri di serie che vengono trovati in seguito. Puoi dare un'occhiata qua:
thinkstats.com/locomotive.py.

Per la domanda 3 bisogna pensarci :-)

.mau. ha detto...

Beh, no: non ne so molto nemmeno di bayesiano. Però mi pare strano poter dire che c'è una probabilità uniforme 1/N, non foss'altro che perché non sappiamo N :-)
Né mi sembra fattibile definire un tetto massimo M e fare probabilità uniforme 1/M: in questo caso, se si estrae il numero k, tutto quello che Bayes ti può dire è che le stime inferiori a k passano a probabilità nulla, ma le altre restano uniformi.

.mau. ha detto...

guardando https://en.wikipedia.org/wiki/German_tank_problem mi pare che l'approccio immagini di avere una distribuzione a priori del numero di carri, scegliere un valore a caso del numero di carri secondo la distribuzione di cui sopra, e infine vedere la probabilità a posteriori che i numeri osservati ci siano.

zar ha detto...

E infatti hai ragione: ho riguardato il programmino, che fa questo. Stabilisce una stima a priori del numero massimo N di carri, e poi assegna una probabilità uniforme a tutti i valori da 1 a N. Poi comincia a estrarre numeri di serie e a aggiornare la probabilità.

.mau. ha detto...

eppure non mi torna. Supponiamo di immaginare di settare M=1000 ed estrarre il numero 8. È chiaro che la probabilità a posteriori che i carri siano 1, 2, ... 7 scende a zero. Ma per gli altri valori non capisco cosa romperebbe la simmetria...

(a meno naturalmente che noi non dicessimo "se ci fossero otto carri abbiamo 1/8 di probabilità a priori che esca 8. Se ce ne fossero 9 abbiamo 1/9 di probabilità a priori; eccetera". Ma da qui a tirare fuori le probabilità a posteriori la vedo dura.

zar ha detto...

Prova a dare un'occhiata al programmino che ho linkato, fa proprio quello che dici. Ogni volta che estrae un nuovo numero di serie aggiorna la distribuzione di probabilità moltiplicando la vecchia per le probabilità di vedere un certo carro immaginando che ci siano N carri.

johnbocchi ha detto...

Premessa necessaria:
sono laureato in matematica, ma adoro la geometria e la topologia algebrica tanto quanto odio il calcolo delle probabilità e la statistica.

Detto ciò, cito:
"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."

Sono indeciso su questa prima e fondamentale considerazione.
Voglio dire, il fatto che le acciaierie degli alleati fossero solite numerare i carri armati in ordine progressivo, non significa che anche quelle dei tedeschi lo facessero.
C'è da dire che gli inglesi, conoscendo la proverbiale rigidità dei tedeschi, a buona ragione potessero supporre che la numerazione progressiva fosse quasi obbligatoria.
Ma rimane il fatto che nessuno ci assicura che fosse così!
Quindi mi chiedo: è corretto dare per scontata un'informazione simile?

zar ha detto...

Assolutamente no, il numero di serie non può dare questa informazione. Credo che ci sia stato anche un po' di spionaggio fatto sul campo, per capire se questo numero fosse affidabile come numero progressivo.

Anonimo ha detto...

Articolo interessante grazie. "Eh, sì, bisognerebbe criptarli in un qualche modo...", aggiungo che si potrebbero usare anche degli UUID in qualche modo... https://en.wikipedia.org/wiki/Universally_unique_identifier