Infinite-Monkey-Theorem

Kernaussage und Bedeutung

Das Infinite-Monkey-Theorem, auch „Theorem der endlos tippenden Affen“, ist ein Gedankenexperiment aus der Wahrscheinlichkeitstheorie. Es besagt: Tippt ein Affe unendlich lange zufällig auf einer Schreibmaschine, wird er fast sicher irgendwann jeden vorgegebenen endlichen Text schreiben – bildlich etwa sämtliche Werke William Shakespeares oder alle Bücher der Bibliothèque nationale de France. „Fast sicher“ bedeutet mathematisch „mit Wahrscheinlichkeit 1“; es bedeutet nicht, dass der Erfolg nach einer bestimmten endlichen Zeit garantiert ist.

Eine Variante betrachtet unendlich viele gleichzeitig tippende Affen. Dann nähert sich die Wahrscheinlichkeit 1, dass mindestens einer einen vorgegebenen Text sofort und fehlerfrei schreibt. Der Affe ist nur ein Symbol für eine zufällige Zeichenproduktion. Die Schreibmaschine und die sehr langen Werke machen die überraschende Wirkung extrem kleiner Wahrscheinlichkeiten in Verbindung mit Unendlichkeit anschaulich.

Das Theorem veranschaulicht insbesondere das Borel-Cantelli-Lemma. Entscheidend ist, dass ein beliebiger Zieltext endlich lang ist und bei jedem unabhängigen Versuch eine positive, wenn auch möglicherweise winzige Trefferwahrscheinlichkeit besitzt. Für einen endlichen Zeitraum bleibt die praktische Erfolgschance bei langen Texten dagegen verschwindend klein.

Berechnung am Beispiel „hamlet“

Im vereinfachten Modell besitzt die Schreibmaschine 50 Tasten. Jede Taste wird bei jedem Anschlag mit der gleichen Wahrscheinlichkeit 1/50 gedrückt; außerdem sind die Anschläge unabhängig. Unabhängigkeit bedeutet, dass ein früherer Anschlag die Wahrscheinlichkeiten der späteren nicht verändert.

Für das sechs Zeichen lange Wort „hamlet“ beträgt die Trefferwahrscheinlichkeit eines Versuchs

p₁ = 1/50⁶.

Das Gegenereignis, also das Verfehlen des Wortes, hat die Wahrscheinlichkeit

p̄₁ = 1 − 1/50⁶.

Bei n unabhängigen Versuchen ist die Wahrscheinlichkeit, „hamlet“ kein einziges Mal zu erhalten,

p̄ₙ = (1 − 1/50⁶)ⁿ.

Dieser Ausdruck strebt für wachsendes n gegen 0. Daher strebt die Wahrscheinlichkeit

pₙ = 1 − p̄ₙ

für mindestens einen Treffer gegen 1.

Allgemein gilt für eine Schreibmaschine mit t Tasten, einen Zieltext der Länge m und eine gewünschte Erfolgswahrscheinlichkeit von mindestens q Prozent:

n ≥ ln(1 − q/100) / ln(1 − 1/tᵐ).

Für „hamlet“ auf 50 Tasten werden für mindestens 10 Prozent Erfolgswahrscheinlichkeit mindestens 1.646.257.350 Versuche benötigt. Für mindestens 90 Prozent sind es mindestens 35.977.876.618 Versuche. Beginnt jeder neue Versuch bereits mit dem jeweils nächsten Zeichen, braucht man für n Versuche n + 5 Anschläge. Bei einem Anschlag pro Sekunde wären für 90 Prozent Erfolg ungefähr 1140 Jahre erforderlich.

Die konkrete Zeichenfolge ist mathematisch unerheblich. Auch ihre Länge ändert die grundsätzliche Annäherung an Wahrscheinlichkeit 1 nicht; ein längerer Text besitzt jedoch eine viel kleinere Trefferwahrscheinlichkeit, sodass die Annäherung erheblich langsamer erfolgt.

Formale Aussage und Größenordnungen

Formal lautet die zentrale Aussage: In einer zufälligen Zeichenfolge unendlicher Länge tritt jede beliebige endliche Zeichenfolge mit Wahrscheinlichkeit 1 mindestens einmal auf – und sogar fast sicher unendlich oft. Ein einziger unendlich lange tippender Affe würde daher sämtliche Werke Shakespeares unendlich oft erzeugen.

Zum Beweis kann die unendliche Zufallsfolge in Blöcke aufgeteilt werden, die jeweils so lang wie der Zieltext sind. Jeder Block bildet ein unabhängiges Ereignis Aₙ mit derselben positiven Trefferwahrscheinlichkeit. Deshalb gilt

Σₙ₌₁^∞ P(Aₙ) = ∞.

Nach dem Borel-Cantelli-Lemma folgt daraus

(Aₙ)ₙ∈ℕ unabhängig und Σₙ₌₁^∞ P(Aₙ) = ∞ ⇒ P(limsup Aₙ) = 1.

Der Limes superior bezeichnet hier das Ereignis, dass Treffer unendlich oft auftreten. Auch das Null-Eins-Gesetz von Kolmogorow und Borel zeigt, dass ein entsprechendes Ereignis eine Wahrscheinlichkeit von 0 oder 1 haben muss.

Endliche Größenordnungen sehen völlig anders aus. Nimmt man nur 26 gleich wahrscheinliche Buchstaben an, beträgt die Wahrscheinlichkeit für den richtigen ersten Buchstaben 1/26 und für die ersten beiden 1/676. Für 20 richtige Buchstaben hintereinander ergibt sich

1/26²⁰ = 1/19 928 148 895 209 409 152 340 197 376.

Hamlet umfasst ohne Interpunktion mehr als 130 000 Buchstaben. Die idealisierte Wahrscheinlichkeit für den gesamten Text bei einem Versuch beträgt

1/26¹³⁰⁰⁰⁰ ≈ 1/(3,4 · 10¹⁸³⁹⁴⁶).

Selbst wenn das sichtbare Universum mit atomgroßen Affen gefüllt wäre, die bis zum Ende des Universums tippten, wäre die Erfolgswahrscheinlichkeit laut der angeführten Modellrechnung viele Größenordnungen kleiner als 10⁻¹³⁸⁸⁰⁰. Charles Kittel und Herbert Kroemer bezeichnen die Wahrscheinlichkeit für Hamlet deshalb für jeden denkbaren praktischen Fall als null. Das widerspricht dem Theorem nicht: Es trennt endliche, physisch mögliche Versuche von einer tatsächlich unendlichen Versuchszahl.

Voraussetzungen, Grenzen und Experimente

Die einfache Rechnung nimmt gleich wahrscheinliche und voneinander unabhängige Tastenanschläge an. Eine Gleichverteilung ist jedoch nicht zwingend notwendig. Die Schlussfolgerung bleibt bestehen, wenn die Anschläge unabhängig sind und die Wahrscheinlichkeit jedes benötigten Zeichens bei jedem Anschlag durch eine strikt positive Konstante nach unten begrenzt ist. Ein Zeichen darf also nicht unmöglich sein.

Das Theorem erzeugt außerdem nicht nur sinnvolle Texte. Neben jedem richtigen Text entstehen unendlich viele unsinnige oder fehlerhafte Varianten. Ohne eine bereits bekannte korrekte Fassung lässt sich der richtige Text nicht zuverlässig von den falschen unterscheiden. Darin zeigt sich eine Grenze der Vorstellung, der Affe könne auf diese Weise verwendbares Wissen schaffen. Ein Bezug besteht zur Entropie der Informationstheorie, die den Informationsgehalt einer Nachricht gegenüber zufälligen Zeichenketten beschreibt, sowie in vereinfachter Form zum zweiten Hauptsatz der Thermodynamik.

Richard Dawkins verwendete ein Computerprogramm mit dem Zielsatz „METHINKS IT IS LIKE A WEASEL“, um zufällige Einzelschritt-Auslese mit kumulativer Auslese zu vergleichen. Bei der kumulativen Auslese bleiben bereits passende Buchstaben erhalten, während nur die übrigen neu erzeugt werden. Dadurch wird das Ziel mit sehr viel weniger Schritten erreicht als durch vollständiges Neuwürfeln. Dawkins betonte, dass dies nur die Wirksamkeit kumulativer Auslese zeigt, nicht die biologische Evolution selbst, denn Evolution ist nicht auf ein vorgegebenes Ziel ausgerichtet.

2003 stellten Wissenschaftler und Studenten im Zoo von Paignton sechs Makaken einen Monat lang eine Computertastatur zur Verfügung. Es entstanden fünf Seiten, die hauptsächlich aus dem Buchstaben S bestanden; außerdem schlugen die Tiere mit einem Stein auf die Tastatur und entleerten sich darüber. Dies war eine künstlerische Darbietung, kein wissenschaftliches Experiment. Allgemein können endlich viele Versuche mit endlicher Dauer keine Aussage über eine unendliche Grundgesamtheit beweisen. Das Infinite-Monkey-Theorem ist daher empirisch nicht beweisbar.

Wissenschaftlicher und kultureller Kontext

Vorläufer des Gedankens reichen bis zu Vergleichen zwischen Atomen und Schriftzeichen zurück. Cicero wandte gegen die atomistische Weltanschauung ein, zufällig zu Boden geworfene Buchstaben würden kaum die Annalen des Ennius bilden. Das moderne Bild der zufällig tippenden Affen erscheint 1913 in Émile Borels Artikel „Mécanique Statistique et Irréversibilité“. Jorge Luis Borges behandelte die Idee der vollständigen Bibliothek in „Die vollständige Bibliothek“ und später in „Die Bibliothek von Babel“: Eine solche Bibliothek enthielte jede wahre Aussage, aber für jede sinnvolle Zeile auch Millionen bedeutungsloser Zeichenfolgen.

Ein häufig Thomas Henry Huxley zugeschriebener Ausspruch von 1860 verbindet sechs ewige Affen mit Shakespeare, dem 23. Psalm und der zufälligen Entstehung komplexer Formen. Ob Huxley dies wirklich sagte, ist umstritten; als Einwand gilt unter anderem, dass sich die Schreibmaschine erst später verbreitete. Arthur Eddington verglich 1928 die Erzeugung aller Bücher des British Museum durch Affen mit der noch geringeren Wahrscheinlichkeit, dass sich sämtliche Moleküle eines Behälters in einer Hälfte sammeln, und stellte damit einen Bezug zur statistischen Physik und zum zweiten Hauptsatz der Thermodynamik her.

Das Motiv wurde vielfach in Literatur, Fernsehen und Computerkultur aufgegriffen, etwa bei Jonathan Swift, Michael Ende, Douglas Adams, den Simpsons und in einem als Aprilscherz veröffentlichten „Infinite Monkey Protocol Suite“ des IETF aus dem Jahr 2000. Diese Verwendungen spielen meist mit dem Gegensatz zwischen theoretischer Möglichkeit und praktischer Unwahrscheinlichkeit.

In Diskussionen über Intelligent Design dient das Theorem manchen Autoren als Bild für die äußerst geringe Wahrscheinlichkeit einer rein zufälligen Entstehung von Leben. Dagegen wird eingewandt, dass biologische Evolution nicht bloß aus zufälliger Zeichen- oder Merkmalsproduktion besteht: Sie wird wesentlich durch nichtzufällige Selektion bestimmt. Damit entspricht sie nicht dem Modell eines Affen, der bei jedem Versuch vollständig von vorn beginnt.