"New Test Sizes Up Randomness," by Charles Seife. Science, 25 April1997, page 532.
Mathematicians have long wrestled with the problem of producing a quantitativemeasure of randomness. This article discusses the work of Steve Pincus andBurton Singer, who have developed a quantitative measure of randomness instrings of digits. According to the article, their idea is built "on theobservation that all possible digits are represented about equally in aperfectly random string of numbers." For example, the string 01101100 hasequally many 0s and 1s. The next step is to examine how the digits come two ata time; if the string of numbers is truly random, the pairs 01, 10, 11, and 00should all appear, and they should appear an equal number of times. The nextstep is to take digits 3 at a time, and so on. By comparing the frequency ofthe groups of digits to the expected frequency, one can calculate a measure ofthe randomness of the sequence. This work has the potential for important usesin cryptography and experimental design.
--- Allyn Jackson