the infinite monkey theorem

The infinite monkey theorem is a thought experiment that has always fascinated me: a monkey pressing keys at random on a typewriter, for an infinite amount of time, eventually produces any given text.

Infinity is not available, but the finite version is — generate random strings until you hit a target one — and I wanted an excuse to write some C++, which is quick enough at tight loops to make the experiment bearable.

the shape of it

Two functions do the work. generate builds a random string of the target’s length: pick a random index into a 26-letter alphabet, take that letter, repeat. score walks the two strings in step and returns the fraction of positions that match, so an identical string scores 1.

Everything else is built on those. testUntilAchieve calls generate until score returns a perfect 1 and reports how many attempts that took. repeatTest runs it many times and averages, which is really a test of the test: the average should land near the number of possible strings, and if it does not, one of the two functions is wrong.

It is worth noting that rand() will hand you the same sequence on every run unless you seed it, so srand() with the current time is doing real work here rather than being ceremony. And score assumes both strings are the same length — it has no defence if they are not.

the number

The expected number of attempts is the size of the alphabet raised to the length of the string. That sounds mild until you write it down:

hello    26^5  =      11,881,376
monkey   26^6  =     308,915,776
typing   26^6  =     308,915,776
banana   26^6  =     308,915,776

Every additional character multiplies the work by twenty-six. Five letters is a few seconds. Seven letters is a coffee. Ten letters is not happening on a laptop, and no amount of C++ rescues you from that — the problem is the exponent, not the language.

where I would take it next

Parallelising repeatTest across threads is the obvious win, since the runs are completely independent of each other, and it buys a constant factor.

The interesting change is a different one: keep the letters you already got right, and only re-roll the rest. That collapses the problem from exponential to something close to linear, and it turns out to have a name — Dawkins’ weasel program, from The Blind Watchmaker. It is also the moment the experiment stops being the infinite monkey theorem, because the theorem’s whole premise is a monkey with no memory. The version that finishes quickly is a version that cheats.

Which is the honest limitation of the whole exercise. This never generates text; it only rediscovers text I already typed in as the target. The generator has no idea what a word is. Bolting a model onto the front of it — something that learns which strings are worth trying — would be a genuinely different project, and a much better one.

The code is at Torus403/InfiniteMonkeyTheorem.