Because it’s Friday: Detecting Cylons

December 11, 2009
By

(This article was first published on Revolutions, and kindly contributed to R-bloggers)

Battlestar Galactica (Ronald D Moore's reimagined version of the rather cheesy 70's sci-fi series) has been my favourite TV series (of any genre) of recent years, so I'm especially excited that Chris Bilder has given me the chance to blog about it. Chris, an Associate Professor in the Department of Statistics at the University of Nebraska-Lincoln, recently published an article in Chance Magazine looking at how a statistical method may have resolved a critical plot point early in the series.

Let's set the scene. Dr Gaius Baltar, a brilliant scientist among a band of 50,000 human refugees from system of planets devastated by the evil robotic Cylon race, has a problem. Some Cylons look just like humans, and may have infiltrated the refugee population. Baltar has invented a blood test that can distinguish humans from Cylons, but it takes 11 hours to test a blood sample, and there's only one testing machine. On screen, Baltar discusses the problem with his imaginary Cylon companion (look, it's complicated, ok?) named Six:

Gaius Baltar: 47,905 people in the fleet. There's 47,905 blood samples. 11 hours to test each one for Cylon indicators.

Six: Well, that'll take a while.

Gaius Baltar: 21,956 days.

Six: 60.1534 years. 

Gaius Baltar: Well, now, let's figure in a few hours for sleep here and there. We'll call that an even 61, shall we?

Chris explains in the article (you can find a PDF preprint here, if you don't subscribe to Chance) that the problem might have been resolved by employing group testing. Rather than testing each blood sample sequentially, Baltar could have mixed a number of blood samples together and tested the combined sample for Cylon characteristics. Assuming the number of Cylon agents in the fleet was small (turns out there were fewer than 10)  this method could rule out whole swaths of subjects with a single test, or conversely identify one or more suspect pools for individual testing. 

Group Testing isn't science-fiction, either: it's used in the real world for testing diseases where the incidence of the disease is rare, but the cost (in time or resources) of testing is high. Group testing is used to screen blood donations for HIV and other viruses, for example.

Of course, the size of the group pooled together for the group test matters: too small, and you're not getting much efficiency out of the group method; too large and you risk invalidating the test by making the active agent (Cylon cells in our case, I guess) too difficult to detect in a highly-diluted sample. In addition to choosing a group size, there are also various procedures you could choose to allocate subjects to groups and how to retest a "positive" group. Chris used R to plot the amount of time (in years) it would have taken Baltar to detect all the cylons in the fleet using various methods and group sizes:

Cylon group testing

Using the "Halving" procedure and a group size of 500 (and assuming 7 Cylons in the fleet), Baltar could have completed his testing in 101 days. In the series, Baltar abandons his testing assuming it could never have been completed. But Baltar was a nasty piece of work anyway, so who knows what he was really thinking?

Chris Bilder: Supplementary Material for Human or Cylon?

To leave a comment for the author, please follow the link and comment on his blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.