The bombe was fast, but not fast enough to test every rotor order of the naval Enigma. In 1940 Turing invented a pencil-and-paper method to rule out most of them before switching on the machines. Because the sheets used in the method were printed in the town of Banbury, his colleagues named it Banburismus.

The method is statistical. And to devise it, Turing reinvented one of the central ideas of modern statistics.

Letters that repeat

Write two messages in German, one beneath the other, and count the places where both have the same letter. Since German uses E, N, R and I a great deal, coincidences are much more frequent than if the letters were drawn at random. In German text, the chance that two aligned letters coincide is around $\frac1{17}$; with random letters it would be $\frac1{26}$.

The Enigma preserves this property in a curious way: if two messages were enciphered with the same sequence of rotor positions, the coincidences of the original text remain coincidences in the enciphered text, because equal letters in the same position become equal letters. If the positions are different, the rate falls to $\frac1{26}$. Counting coincidences therefore gives evidence that two messages are aligned, and that revealed information about the rotor positions.

What one coincidence is worth

Turing asked: how much should a single coincidence increase my confidence that the messages are aligned? The answer is the likelihood ratio, how many times more likely it is to see a coincidence in one case than in the other:

$$\frac{\text{chance of coincidence if aligned}}{\text{chance if not aligned}}=\frac{1/17}{1/26}=\frac{26}{17}\approx1.53.$$

A place without a coincidence is evidence in the opposite direction, much weaker:

$$\frac{16/17}{25/26}=\frac{416}{425}\approx0.979.$$

By Bayes’ theorem, each piece of evidence multiplies the odds (the ratio between the probability of one hypothesis and that of the other) by its likelihood ratio. With many places, that is many multiplications, and multiplying by hand is slow.

Adding instead of multiplying

Turing did what Napier had done three centuries earlier: he moved to logarithms, to turn multiplications into additions. He called the decimal logarithm of a likelihood ratio a ban, and a tenth of it a deciban:

$$\text{weight in decibans}=10\log_{10}(\text{likelihood ratio}).$$

Now each coincidence is worth

$$10\log_{10}\frac{26}{17}\approx+1.8\ \text{decibans},$$

and each place without a coincidence is worth

$$10\log_{10}\frac{416}{425}\approx-0.09\ \text{decibans}.$$

The operators in Hut 8 only had to count and add. A total of $+20$ decibans means the evidence has made the hypothesis $10^2=100$ times more likely, in terms of odds, than it was before.

Exercise: add up the evidence

Two messages aligned over 200 places have 14 coincidences. What is the total weight in decibans? Has the alignment hypothesis become more likely?

There are 14 coincidences and 186 places without one: $14\cdot1.8+186\cdot(-0.09)\approx25.2-16.7=8.5$ decibans. Positive: the odds in favour of alignment have been multiplied by about $10^{0.85}\approx7$. With random letters, the expected number would be $200/26\approx7.7$ coincidences; with alignment, $200/17\approx11.8$. Fourteen fits alignment better.

Exercise: how many coincidences break even?

Over 100 places, how many coincidences $k$ give a total weight of zero?

$1.8k-0.09(100-k)=0$, that is, $1.89k=9$, and $k\approx4.8$. With 5 coincidences or more in 100 places, the evidence already tips towards alignment. That number lies between the random expectation, $100/26\approx3.8$, and the aligned expectation, $100/17\approx5.9$.

Sources: I. J. Good, “Studies in the history of probability and statistics XXXVII: A. M. Turing’s statistical work in World War II”, Biometrika (1979) · Andrew Hodges, Alan Turing: The Enigma (1983) · Sharon Bertsch McGrayne, The Theory That Would Not Die (2011).

All topics on Alan Turing · ← The Enigma: 159 quintillion keys and one flaw · The imitation game: can a machine think? →

Image credits.