# German tank problem

Das German tank problem (englisch für Problem der deutschen Panzer) oder Taxiproblem besteht in der Wahrscheinlichkeitstheorie darin, das Maximum einer diskreten Gleichverteilung durch eine Stichprobenziehung ohne Zurücklegen abzuschätzen.
Das Problem ist nach seiner Anwendung durch die alliierten Streitkräfte im Zweiten Weltkrieg zur Schätzung der monatlichen Produktionsrate der deutschen Panzer benannt, wobei die deutschen Herstellungspraktiken ausgenutzt wurden. Dabei wurden fortlaufend aufsteigende Seriennummern für verschiedene Panzerbauteile (Fahrgestell, Getriebe, Motor, Räder) vergeben, die anschließend in geringem Umfang in die Hände der alliierten Streitkräfte fielen. Übertragen kann das Problem auch auf andere zufällig beobachtete Seriennummern (wie Taxi-Nummern oder verkaufte Produkte) angewendet werden.
Als mathematisches Problem werden die Seriennummern als ununterbrochene Folge von ganzen Zahlen, beginnend mit der Seriennummer 1, modelliert; die deutsche Herstellungspraxis und die Kennzeichnungskonventionen im Kriegsumfeld waren komplexer und werden hier nicht behandelt.
Das Problem kann entweder mit Hilfe von frequentistischer Inferenz oder Bayesscher Inferenz angegangen werden, wobei unterschiedliche Ergebnisse erzielt werden. Die Schätzung des Maximums der Grundgesamtheit auf der Grundlage einer einzigen Stichprobe ergibt unterschiedliche Ergebnisse, wohingegen die Schätzung auf der Grundlage mehrerer Stichproben eine praktische Schätzfrage ist, deren Antwort einfach (vor allem in der frequentistischen Variante), aber nicht offensichtlich (vor allem in der Bayesschen Variante) ist.

## Annahmen

Es wird angenommen, dass der Gegner eine Reihe von Panzern hergestellt hat, die mit fortlaufenden Ganzzahlen gekennzeichnet sind, beginnend mit der Seriennummer 1. Unabhängig vom Herstellungsdatum des Panzers, der Betriebsgeschichte oder der Seriennummer, die er trägt, sind die ermittelten Seriennummern bis zum Zeitpunkt der Analyse gleichmäßig verteilt.

## Berechnung

Die Formel für die Schätzung der Gesamtzahl der Panzer $N$ basierend auf der Anzahl der Stichproben $k$ und der größten beobachteten Seriennummer $m$ im Rahmen des frequentistischen Ansatzes lautet
    $N\approx m+{\frac {m}{k}}-1,$
während die bayessche Analyse (primär) eine Wahrscheinlichkeitsverteilung für die Anzahl der Panzer liefert
    $P(N=n)={\begin{cases}0&{\text{wenn }}n<m\\{\frac {k-1}{k}}{\frac {\binom {m-1}{k-1}}{\binom {n}{k}}}&{\text{wenn }}n\geq m,\end{cases}}$
aus der der Erwartungswert $\mu$ und die Standardabweichung $\sigma$ für die Anzahl der Panzer gemäß folgender Formel ermittelt werden kann:
    ${\begin{aligned}\mu &=m+{\frac {m-1}{k-2}}-1&&{\text{falls }}k\geq 3,\\\sigma &={\sqrt {\frac {(k-1)(m-1)(m-k+1)}{(k-3)(k-2)^{2}}}}&&{\text{falls }}k\geq 4.\end{aligned}}$

## Beispiel

Angenommen, $k=4$ Panzer mit den Seriennummern 19, 40, 42 und 60 werden erbeutet. Die maximal beobachtete Seriennummer ist $m=60$. Die unbekannte Gesamtzahl der Panzer wird mit $N$ bezeichnet.
Die frequentistische Formel liefert in dem Fall
    $N\approx m+{\frac {m}{k}}-1=74$,
während mit der bayesschen Analyse eine Verteilung ermittelt werden kann, die folgenden Schätzwert liefert:
    $N\approx \mu \pm \sigma =88{,}5\pm 50{,}22$.
Diese Verteilung besitzt eine positive Schiefe, was damit zusammenhängt, dass es mindestens 60 Panzer gibt.

## Historisches Problem

Im Verlauf des Krieges unternahmen die Westalliierten intensive Anstrengungen, um das Ausmaß der deutschen Fertigung zu bestimmen, und näherten sich dem auf zweierlei Weise: konventionelle Informationsgewinnung und statistische Schätzung. In vielen Fällen übertraf die statistische Analyse die herkömmliche Nachrichtentechnik erheblich. In einigen Fällen wurde konventionelle Nachrichtentechnik in Verbindung mit statistischen Methoden eingesetzt, wie es bei der Schätzung der Produktion von Panther-Panzern kurz vor dem D-Day der Fall war.
Die alliierte Kommandostruktur hatte vermutet, dass die in Italien gesehenen Panzerkampfwagen V Panther mit ihren schnellen, langgestreckten 7,5-cm-KwK 42/L70 Kanonen ungewöhnlich schwere Panzer darstellten und nur in geringer Zahl in Nordfrankreich zu sehen waren, ähnlich wie der Tiger I in Tunesien gesehen wurde. Die US-Armee war zuversichtlich, dass der Sherman-Panzer auch weiterhin eine gute Leistung bringen würde, wie auch gegen den Panzerkampfwagen III und Panzerkampfwagen IV in Nordafrika und Sizilien. Kurz vor dem D-Day gab es Gerüchte, dass eine große Anzahl von Panther-V-Panzern im Einsatz war.
Um diese Information zu verifizieren, versuchten die Alliierten die Anzahl der produzierten Panzer abzuschätzen. Dazu benutzten sie die Seriennummern von eroberten oder zerstörten Panzern. Als Hauptnummern wurden Getriebezahlen verwendet, da diese in zwei ununterbrochene Zahlenreihen fielen. Es wurden auch Fahrgestell- und Motornummern verwendet, die allerdings komplizierter zu handhaben waren. Verschiedene andere Komponenten wurden verwendet, um die Analyse zu überprüfen. Ähnliche Analysen wurden an Rädern durchgeführt, bei denen beobachtet wurde, dass sie fortlaufend nummeriert waren (d. h. 1, 2, 3, …, N). (Die untere Schranke war unbekannt, aber um die Diskussion zu vereinfachen, wird dieses Detail in der Regel weggelassen, wobei die untere Schranke als 1 angenommen wird.)
Die Analyse der Panzerräder ergab eine Schätzung der Anzahl der verwendeten Gussformen. Eine Diskussion mit britischen Laufradherstellern schätzte dann die Anzahl der Räder, die aus diesen vielen Formen hergestellt werden konnten, was die Anzahl der Panzer ergab, die jeden Monat produziert wurden. Die Analyse der Räder von zwei Panzern (32 Laufräder, 64 Laufräder insgesamt) ergab eine Schätzung von 270 Panzern, die im Februar 1944 produziert wurden, wesentlich mehr als bisher vermutet.
Deutsche Aufzeichnungen nach dem Krieg zeigten, dass die Produktion für den Monat Februar 1944 bei 276 lag. Der statistische Ansatz erwies sich als weitaus genauer als herkömmliche nachrichtendienstliche Methoden, und der Ausdruck „German tank problem“ wurde als Bezeichnung für diese Art der statistischen Analyse akzeptiert.
Diese Seriennummernanalyse wurde nicht nur zur Abschätzung der Produktion eingesetzt. Sie diente auch dazu, die deutsche Produktionsstruktur allgemeiner zu verstehen, einschließlich der Anzahl der Fabriken, der relativen Bedeutung der Fabriken, der Länge der Lieferkette (basierend auf der Verzögerung zwischen Produktion und Nutzung), der Veränderungen in der Produktion und der Verwendung von Ressourcen wie Gummi.

### Spezifische Daten

Nach herkömmlichen Schätzungen des britischen Geheimdienstes und des US-Geheimdienstes OSS produzierten Industriebetriebe im Großdeutschen Reich zwischen Juni 1940 und September 1942 monatlich rund 1400 Panzer. Man wendete die hier behandelte Formel auf die Seriennummern der erbeuteten Panzer an und kam so auf 246 Panzer pro Monat. Nach Kriegsende zeigten Produktionszahlen aus dem Reichsministerium für Bewaffnung und Munition, dass tatsächlich durchschnittlich 245 Panzer produziert worden waren.
Die Schätzungen für einige Monate werden wie folgt angegeben:
| Monat | Statistische Schätzung | Geheimdienst-Schätzung | Deutsche Aufzeichnungen |
| Juni 1940 | 169 | 1000 | 122 |
| Juni 1941 | 244 | 1550 | 271 |
| August 1942 | 327 | 1550 | 342 |

## Ähnliche Analysen

Ähnliche Seriennummernanalysen wurden während des Zweiten Weltkriegs auch für andere militärische Ausrüstungsgegenstände verwendet, am erfolgreichsten für die V2-Rakete.
Der deutsche Geheimdienst analysierte während des Zweiten Weltkriegs (Deutsch-Sowjetischer Krieg) Fabrikmarkierungen auf sowjetischen Militärausrüstungen. Auch während des Koreakrieges wurden Markierungen auf sowjetischen Militärausrüstungen analysiert.
In den 1980er Jahren erhielten einige Amerikaner Zugang zur Produktionslinie der israelischen Merkava-Panzer. Die Produktionszahlen waren geheim, aber die Panzer hatten Seriennummern, die eine Abschätzung der Produktion ermöglichten.
Die Formel wurde in nicht-militärischen Zusammenhängen verwendet, z. B. um die Zahl der gebauten Commodore-64-Computer zu schätzen, wobei das Ergebnis (12,5 Millionen) mit den unteren Schätzungen übereinstimmt. Auch die Produktionszahlen von iPhones und anderen Mobiltelefonen wurden anhand der IMEI-Nummer mit dieser Methode abgeschätzt.

## Gegenmaßnahmen

Um die Analyse von Seriennummern zu verhindern, können Seriennummern vermieden werden bzw. brauchbare Zusatzinformationen reduziert werden. Alternativ können einer Kryptoanalyse widerstehende Seriennummern verwendet werden, am effektivsten durch die zufällige Ziehung von Nummern ohne Zurücklegen aus einer Liste, die viel größer ist als die Anzahl der produzierten Gegenstände, oder durch die Erzeugung von Zufallszahlen und deren Vergleich mit der Liste der bereits zugewiesenen Nummern; Kollisionen sind wahrscheinlich, es sei denn, die Anzahl der möglichen Ziffern ist mehr als doppelt so hoch wie die Anzahl der Ziffern in der Anzahl der produzierten Objekte (wobei die Seriennummer in jeder beliebigen Basis sein kann); siehe Geburtstagsparadoxon. Hierfür kann ein kryptographisch sicherer Pseudozufallszahlengenerator verwendet werden. Alle diese Methoden erfordern eine Lookup-Tabelle (oder das Brechen der Chiffre), um von der Seriennummer die Produktionsreihenfolge zu ermitteln, was die Verwendung der Seriennummern erschwert: Ein Bereich von Seriennummern kann beispielsweise nicht abgerufen werden, sondern muss einzeln nachgeschlagen oder eine Liste muss erstellt werden. Ein typisches Nummerierungsschema, welches auf Zufallszahlen basiert, ist etwa der Universally Unique Identifier.
Alternativ können fortlaufende Seriennummern mit einer einfachen Substitutionschiffre verschlüsselt werden, was eine einfache Dekodierung ermöglicht, aber auch leicht durch einen Known-Plaintext-Angriff gebrochen werden kann: Auch wenn der Klartext von einem beliebigen Punkt aus gestartet wird, hat er ein Muster (d. h. die Zahlen sind aufeinanderfolgend). Ein Beispiel ist Ken Folletts Roman „Das zweite Gedächtnis“, in dem die Verschlüsselung der Seriennummern der Jupiter-C-Rakete beschrieben wird:
| H | U | N | T | S | V | I | L | E | X |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
Das Codewort hier ist Huntsville (ohne wiederholte Buchstaben), um einen Schlüssel mit 10 Buchstaben zu erhalten. Die Rakete Nummer 13 war also „HN“, und die Rakete Nummer 24 war „UT“.
Eine starke Verschlüsselung von Seriennummern, ohne diese zu vergrößern, kann mit Format-erhaltender Verschlüsselung erreicht werden. Anstatt eine wirklich zufällige Permutation auf der Menge aller möglichen Seriennummern in einer großen Tabelle zu speichern, leiten solche Algorithmen eine pseudozufällige Permutation von einem geheimen Schlüssel ab. Sicherheit kann dann definiert werden als die pseudozufällige Permutation, die von einer wirklich zufälligen Permutation für einen Angreifer, der den Schlüssel nicht kennt, nicht zu unterscheiden ist.