Neulich bin ich (im NKRC-Forum) über das Infinite-Monkey-Theorem gestolpert. Dieses besagt, dass wenn ein Affe unendlich lange auf einer Schreibmaschine tippt, er irgendwann die kompletten Werke Shakespeares geschrieben haben wird. Dies lässt sich durch simple Wahrscheinlichkeitsrechnung sehr einfach nachweisen. Irgendwie hatte man schon mal davon gehört (unter anderem wird es im Anhalter referenziert), und die wissenschaftlichen Ausführungen des Artikels fand ich faszinierend, so dass ich mich etwas näher damit beschäftigt habe. Hängen geblieben bin ich beim simulierten Affen, der im Jahr 2004 tatsächlich mit einigen Wörtern aus Shakespeare-Werken aufwarten konnte:
One computer program run by Dan Oliver of Scottsdale, Arizona, according to an article in The New Yorker, came up with a result on August 4, 2004: After the group had worked for 42,162,500,000 billion billion monkey-years, one of the “monkeys” typed, “VALENTINE. Cease toIdor:eFLP0FRjWK78aXzVOwm)-‘;8.t” The first 19 letters of this sequence can be found in “The Two Gentlemen of Verona”. Other teams have reproduced 18 characters from “Timon of Athens”, 17 from “Troilus and Cressida”, and 16 from “Richard II”.
Dadurch inspiriert habe ich mir einen eigenen kleinen tippenden Affen programmiert, dem ich das Leben allerdings ein wenig leichter machen wollte und ihm deshalb nur eine Tastatur mit den Großbuchstaben von A bis Z zur Verfügung gestellt habe. Man muss ja nicht gleich mit Shakespeare loslegen, einzelne Wörter tun es vorerst auch. Dabei werden immer ganze Wörter betrachtet, das heißt, wenn wir “ROMEO” sehen wollen, muss das in einem Block von 5 Buchstaben passieren. Diese Einschränkung kann man sich so vorstellen, dass der Affe alle fünf Buchstaben ein Leerzeichen einfügt. “ABROM EO” würde also nicht als gültiger Versuch zählen, auch wenn “ROMEO” darin enthalten ist, “ABCDE ROMEO” wäre dagegen gültig.
Es stellt sich heraus, dass der Affe Wörter aus vier Buchstaben recht schnell beisammen hat (Wahrscheinlichkeit (1/26 ) 4 = 0,000002188298729 für ein bestimmtes Wort in einem 4er-Buchstabenblock), meist nach unter 1 Million Versuchen. Bei Wörtern mit 5 Buchstaben sind wir bei einigen Versuchen schon im zweistelligen Millionenbereich (Wahrscheinlichkeit (1/26) 5 = 0,000000084165336):
Monkey typed ROMEO after 9426431 tries (47132155 letters) Monkey typed JULIA after 4057636 tries (20288180 letters) Monkey typed ROMEO after 2878262 tries (14391310 letters) Monkey typed JULIA after 35647563 tries (178237815 letters) Monkey typed ROMEO after 17810361 tries (89051805 letters) Monkey typed JULIA after 1898056 tries (9490280 letters)
Da aber eh alles nur Zufall ist, kommt der Affe manchmal auch recht schnell zum gewünschten Wort:
Monkey typed JULIA after 173549 tries (867745 letters)
Bei sechs Buchstaben (Wahrscheinlichkeit (1/26) 6 = 0,000000003237128) wirds schon recht hart, obwohl der Affe sich größte Mühe gibt. Meine Affensimulationsworkstation muss erstmals den Lüfter ordentlich ankurbeln:
Monkey typed HAMLET after 603904436 tries (3623426616 letters)
Das Spielchen könnte man nun noch ewig (a.k.a. “unendlich”) weitertreiben, und je länger der Affe tippt, desto kleiner wird die Wahrscheinlichkeit des Gegenereignisses “Affe tippt nicht HAMLET”: Diese Wahrscheinlichkeit entspricht für einen Versuch mit 6 Buchstaben 1 – (1/26) 6 = 0,999999996762872. Für 1 Million Versuche mit 6 Buchstaben (= 6 Millionen getippten Buchstaben) entspricht die Wahrscheinlichkeit, dass der Affe nicht “HAMLET” getippt hat nur noch (1 – (1/26) 6) 1000000 = 0,996768105391838. Drauf zu wetten wäre immer noch recht riskant, aber man sieht wo es hinführt. Bei 220 Millionen ausprobierten 6-Buchstabenkombinationenn (= 1,32 Milliarden getippten Buchstaben) beträgt die Wahrscheinlichkeit, dass nicht “HAMLET” getippt wurde nur noch 0,490579339348471 und tendiert mit unendlich vielen Versuchen folglich gegen 0.
Um zurück in die Wirklichkeit zu kommen: Wäre der Affe echt – sagen wir mal ein Schimpanse – und hätte Spaß am tippen auf einer Tastatur mit 26 Buchstaben von A bis Z, wie lange bräuchte er für ein bestimmtes Wort mit 5 Buchstaben? Wenn er wirklich verrückt nach Tastaturen wäre, nehmen wir an, er würde 8 Stunden pro Tag mit 60 Anschlägen pro Minute auf der Tastatur hämmern. Damit würde er 28800 Buchstaben pro Tag tippen, also, wenn wir einmal davon ausgehen, dass wir “ROMEO” mit 5 Buchstaben sehen wollen, 5760 Versuche pro Tag absolvieren. Der Affe bekommt an seinem ersten Geburtstag eine Schreibmaschine geschenkt und beginnt mit dem tippen bis zu seinem Lebensende mit 40, dann würde er, bei einem Ruhetag pro Woche, in einem Jahr 1797120 Versuche durchführen – das macht in 39 Jahren 70087680 Versuche. Die Wahrscheinlichkeit, dass er in 70087680 Versuchen nicht “ROMEO” schreibt, beträgt (1 – (1/26) 5) ^70087680 = 0,002742313521483. Es ist also sehr unwahrscheinlich, dass unser Affe in seiner Lebenszeit nicht einmal “ROMEO” schreiben wird. Schon nach rund 8,3 Millionen Versuchen, was in etwa 4,6 Jahren entspricht, ist es wahrscheinlicher, dass er “ROMEO” geschrieben haben wird, als dass er es nicht geschrieben haben wird. Wollen wir dagegen “HAMLET” sehen, ist die Wahrscheinlichkeit mit 0,827729375129488 schon recht groß, dass der Affe es in seiner Lebenszeit nicht schreiben wird.
Das Infinite-Monkey-Theorem ist auf jeden Fall ein faszinierendes Gedankenexperiment, mit dem man gerne mal einen Sonntagnachmittag verbringen kann. Und damit man kein armes Äffchen vor eine Schreibmaschine setzen muss, gibt es hier den Ruby-Quelltext für die Affensimulation:
####################
# monkey simulator
####################
# USAGE:
# ruby monkey.rb [WORD]
####################
# take a word as argument
word = ARGV[0]
#if no word was given make it "BANANA"
word = word != nil ? word : "BANANA"
store = []
tries = 0
while(store.size != word.size) do
word.each_byte do |letter|
rand_letter = rand(26) + 65
if(letter != rand_letter)
store = []
tries += 1
break
else
store << letter.chr
if(store.size > 3)
puts "Monkey typed #{store.join('')} after #{tries} tries (#{tries * word.size} letters)"
end
end
end
end
