Monday, October 3, 2011

Don’t give up hope on “random”

Japanese macaques, AP 

Discussions of random processes often include this thought experiment. Here is a “live” test… reported by the BBC.

A few million virtual monkeys are close to re-creating the complete works of Shakespeare by randomly mashing keys on virtual typewriters.

A running total of how well they are doing shows that the re-creation is 99.990% complete. The first single work to be completed was the poem A Lover's Complaint.

Set up by US programmer Jesse Anderson the project co-ordinates the virtual monkeys sitting on Amazon's EC2 cloud computing system via a home PC.

Mr Anderson said he started the project as a way to get to know the Hadoop programming tool better and to put Amazon's web services to the test.

It is also a practical test of the thought experiment that wonders whether an infinite number of monkeys pounding on an infinite number of typewriters would be able to produce Shakespeare's works by accident.

Mr Anderson's virtual monkeys are small computer programs uploaded to Amazon servers. These coded apes regularly pump out random sequences of text.

Each sequence is nine characters long and each is checked to see if that string of characters appears anywhere in the works of Shakespeare. If not, it is discarded. If it does match then progress has been made towards re-creating the works of the Bard.

To get a sense of the scale of the project, there are about 5.5 trillion different combinations of any nine characters from the English alphabet.

Mr Anderson's monkeys are generating random nine-character strings to try to produce all these strings and thereby find those that appear in Shakespeare's works.

Mr Anderson kicked off the project on 21 August using Amazon's cloud computers. Each day of virtual monkey keyboard mashing processing cost $19.20 (£12.40).

The project has been moved to a home PC to speed up text string generation and to cut the cost. To make the task even easier the text being sampled has had all the spaces and punctuation removed.

Mathematicians said the constraints Mr Anderson introduced to the project mean he will complete it in a reasonable amount of time.

Monkeys: More interested in throwing faeces than writing sonnets

"If he's running an evolutionary approach, holding on to successful guesses, then he'll get there," said Tim Harford, popular science writer and presenter of the BBC's radio show about numbers More or Less.

And without those constraints?

"Not a chance," said Dr Ian Stewart, emeritus professor of mathematics at the University of Warwick.

His calculations suggest it would take far, far longer than the age of the Universe for monkeys to completely randomly produce a flawless copy of the 3,695,990 or so characters in the works.

"Along the way there would be untold numbers of attempts with one character wrong; even more with two wrong, and so on." he said. "Almost all other books, being shorter, would appear (countless times) before Shakespeare did."

Earlier experiments have shown how difficult the task is. Wikipedia mentions a 2003 project that used computer programs to simulate a lot of monkeys randomly typing.

After the equivalent of billions and billions and billions of monkey years the simulated apes had only produced part of a line from Henry IV, Part 2.

Also in 2003, Paignton Zoo carried out a practical test by putting a keyboard connected to a PC into the cage of six crested macaques. After a month the monkeys had produced five pages of the letter "S" and had broken the keyboard.


No comments:

Post a Comment