Feeds

Achtung! Use maths to smash the German tank problem – and your rival

Leaky data is a double agent in intelligence analysis

Choosing a cloud hosting partner with confidence

Big Data's Big 5 You've employed Benford's Law to out fraudsters hidden in seemingly random numbers. Now what do you do if you need answers but some of your data is missing? Welcome to the German tank problem, the second in The Reg's guide to crafty techniques from the world of mathematics that can help you quickly solve niggling data problems.

The German Tank problem (and its solution) can allow you to estimate data that you don’t have in order to gain information that you want. A more formal statement of this process is: “The estimation of the maximum of a discrete uniform distribution by sampling (without replacement).” The less formal title, though, is snappier and gives a huge clue as to the provenance.

During the Second World War, the British became very interested in the number of tanks the Germans were producing. Intelligence sources suggested the production was about 1,000 to 1,500 tanks per month. In practice it was nowhere near that high and the wily British boffins found another much more accurate way of estimating production.

They got the squaddies on the battlefield to examine as many captured/disabled tanks as they could and collect all the serial numbers they could find. (In truth this must have been highly exasperating for the soldiers, who probably felt that knocking the tank out in the first place was good enough)

Let’s assume for a moment that tank serial numbers are simple. They all have numbers taken from the same series; the series starts at “1” and increments by one for each new tank.

If we find a tank with the serial number 24 then the Germans have produced at least 24 tanks. However we can be a bit smarter than that. Suppose we see the following numbers: 23, 16, 24, 17, 11, 6, 7, 9 and 12.

That’s nine numbers between seven and 24. If there were actually 4,000 tanks out there, it would seem highly unlikely that our sample would just happen to come from the first 24 produced. It is much more likely that there are only about 30-40 tanks in all out there. (To put that slightly more formally, it is likely that the entire population from which we have drawn our sample is around 30-40.)

And we can be even smarter. Suppose we examine five tanks (we’ll call the number of examined tanks E, so E=5) with serial numbers of: 432, 3245, 2187, 435, 1542.

The biggest serial number (which we’ll call B) is 3,245, and the smallest (s) is 432. We could reasonably expect as many ‘hidden’ numbers – serial numbers we guess must be out there but for which we have no data – above 3,245 as there are below 432.

In our nomenclature, n is our estimate of the number of tanks.

To put that graphically:

German tank line chart

And to put it mathematically:

we hypothesised that (n-B) is roughly equal to (s-1), so if:

n-B = s-1

then we can say that: n=B+(s-1)

which we can solve for n by slotting in the actual numbers.

In our case B=3,245, s=432, n=number of tanks produced, so:

n= 3,245 + (432-1) = 3,676

This is merely one formula for estimating the maximum of a discrete uniform distribution by sampling (without replacement). We can also use:

n = (1+1/E)*B

E, if you remember, is the number of tanks examined, which was five, so:

n = (1 +1/5)*3,245 = 3,894

This particular formula was proposed (PDF) by Roger Johnson of Carleton College in Northfield, Minnesota in the journal Teaching Statistics, Volume 16, Number 2, Summer 1994

You might also wish to try a Bayesian approach. I have no particular axe to grind here. I don’t mind how you do it; the important point is that you can.

Now, as it happens, there are several over-simplifications in my original description, both in the reality of WWII and also if we were trying to solve the same kind of problem today.

Business security measures using SSL

More from The Register

next story
'Windows 9' LEAK: Microsoft's playing catchup with Linux
Multiple desktops and live tiles in restored Start button star in new vids
Not appy with your Chromebook? Well now it can run Android apps
Google offers beta of tricky OS-inside-OS tech
New 'Cosmos' browser surfs the net by TXT alone
No data plan? No WiFi? No worries ... except sluggish download speed
SUSE Linux owner Attachmate gobbled by Micro Focus for $2.3bn
Merger will lead to mainframe and COBOL powerhouse
iOS 8 release: WebGL now runs everywhere. Hurrah for 3D graphics!
HTML 5's pretty neat ... when your browser supports it
Greater dev access to iOS 8 will put us AT RISK from HACKERS
Knocking holes in Apple's walled garden could backfire, says securo-chap
NHS grows a NoSQL backbone and rips out its Oracle Spine
Open source? In the government? Ha ha! What, wait ...?
Google extends app refund window to two hours
You now have 120 minutes to finish that game instead of 15
Intel: Hey, enterprises, drop everything and DO HADOOP
Big Data analytics projected to run on more servers than any other app
prev story

Whitepapers

Providing a secure and efficient Helpdesk
A single remote control platform for user support is be key to providing an efficient helpdesk. Retain full control over the way in which screen and keystroke data is transmitted.
Saudi Petroleum chooses Tegile storage solution
A storage solution that addresses company growth and performance for business-critical applications of caseware archive and search along with other key operational systems.
Security and trust: The backbone of doing business over the internet
Explores the current state of website security and the contributions Symantec is making to help organizations protect critical data and build trust with customers.
Reg Reader Research: SaaS based Email and Office Productivity Tools
Read this Reg reader report which provides advice and guidance for SMBs towards the use of SaaS based email and Office productivity tools.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.