| |
| Autor |
 Infinite Monkey Theorem |
|
tati_mathi
Neu 
Dabei seit: 27.06.2022
Mitteilungen: 1
 |  Themenstart: 2022-06-27
|
Hey,
ich beschäftige mich gerade mit einer Aufgabe, in der es um das Infinite Monkey Theorem geht. Für die Leute, die nicht wissen worum es geht: Es besagt, dass wenn ein Affe willkürlich auf einer Schreibmaschine tippt, wird er in unendlicher Zeit eine endliche Zeichenfolge, so auch ein Werk von Shakespear, schreiben. Ansonsten ist es auch sehr gut auf Wikipedia beschrieben.
Die Beweisidee mit dem Borel-Cantelli-Lemma oder auch die etwas intuitivere Version mit der Gegenwahrscheinlichkeit: \(1-(\frac{1}{N})\) etc. ist für mich kein Problem. Bei mir hapert es dabei, einen passenden Wahrscheinlichkeitsraum zu definieren.
Ich habe mir schon folgendes überlegt:
\[p_\omega=\bigg(\frac{1}{N}\bigg)^j\], wobei \(j\) die Menge der Zeichen von \(\omega\) ist und \(N\) die Anzahl der Zeichen auf der Schreibmaschine
Weiter komme ich momentan nicht.
Ich bedanke mich schon mal für jeden Hinweis und Tipp :)
LG Tatjana
|
 Profil
| Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten |
Bozzo
Senior 
Dabei seit: 11.04.2011
Mitteilungen: 2300
Wohnort: Franken
 | Beitrag No.1, eingetragen 2022-07-01
|
Hallo Tatjana,
zunächst mal wird der Affe nicht "eine endliche Zeichenfolge", sondern "JEDE endliche Zeichenfolge" schreiben.
Deiner Notation folgend vermute ich, dass \(\omega\) eine beliebige solche endliche Zeichenfolge sein soll (mit j Buchstaben aus einem Alphabet mit N Buchstaben) und du nun beweisen möchtest, dass der Affe auch diese Zeichenfolge \(\omega\) tippen wird.
Zunächst mal möchte ich ein Vorraussetzungen explizit machen, die benötigt werden, damit das überhaupt stimmt. Und zwar wird angenommen, dass der Affe jeden einzelnen Buchstaben gleichverteilt zufällig tippt und unabhängig von den bisherigen Buchstaben. In der Praxis wäre das wahrscheinlich eher nicht so. Wenn ich "zufällig" auf meiner Tastatur rumdrücke, kommen dabei wahrscheinlich wesentlich öfter die Buchstaben "asdfjklö" vor als die übrigen, weil die "am besten" liegen, Kleinbuchstaben und Großbuchstaben würden jeweils gehäuft vorkommen (im Wechsel immer dann, wenn ich die Caps-Lock-Taste erwische), und wahrscheinlich hätte ich auf einen Buchstaben aus der linken Tastaturhälfte mit größerer Wahrscheinlichkeit einen aus der rechten Tastaturhälfte folgend, da ich beim wild Herumklimpern dazu neige, meine beiden Hände abwechselnd zu bewegen. Und würde dem Affen schließlich irgendwann langweilig werden und er nur noch abwechselnd asasasa... tippen, käme schlussendlich auch kein Shakespeare dabei heraus. D. h. diese "zufällig gleichverteilt und unabhängig"-Annahme ist schon eine deutliche Einschränkung für das "Experiment".
Der nächste wichtige Punkt im Beweis ist, dass man sich nicht nur überlegt, ob eine bestimmte Zeichenkette irgendwo vorkommt, sondern sie muss sogar an einer bestimmten Stelle in einem Raster stehen. Würde man z. B. in dem folgenden "Text" nach "HUT" suchen:
abHUTd hlvo balHUTan delebe
so findet man es zwei mal. In dem typischen Beweis wird der Text allerdings zunächst mal in Blöcke der Länge 3 geteilt (weil das "Suchwort" 3 Buchstaben hat und der Text wiefolgt betrachtet:
|abH|UTd| hl|vo |bal|HUT|an |del|ebe|
Das erste "HUT" wird hier gar nicht berücksichtigt, weil es "zwischen" zwei Rasterwörtern steht und nur das zweite HUT würde berücksichtigt werden. Da ja nur gefragt wird, ob "HUT" überhaupt vorkommen muss, und der Beweis zeigt, dass es sogar schon auch irgendwann einmal "im Raster" vorkommen muss, reicht das auch schon aus. Das macht den Beweis etwas leichter, aber vlt. auch etwas unerwarteter.
Betrachten wir nur die Zeichenkette "abHUTd" und würden wir uns fragen, ob "HUT" irgendwo vorkommt, müssten wir "abH", "bHU", "HUT" und "UTd" prüfen. Diese Wörter sind aber nicht unabhängig, da die ersten beiden Buchstaben des jeweils folgenden Wortes mit den letzten beiden Buchstaben des vorherigen übereinstimmen, was die ganze Rechnung deutlich verkomplizieren würde. D. h. zuletzt wird dann auch nur die Wahrscheinlichkeit, dass die Zeichenkette vorkommt nach unten abgeschätzt. Da diese Abschätzung nach unten allerdings schon zu einer W'kt von mind. 1 führen wird, stellt das am Ende kein Problem mehr da.
Du hast mit \(p_\omega\) nun die W'kt berechnet, dass die gesuchte Zeichenkette an einer bestimmten Stelle im gerasterten Text vorkommt. Jetzt kannst du dir im nächsten Schritt überlegen, wie groß die W'kt ist, dass an dieser Stelle ein beliebiger anderer Text als der gesuchte steht. Wie groß ist diese? Dann kannst du dir damit überlegen, wie groß die Wahrscheinlichkeit ist, dass der gesuchte Text in keiner der \(n\) ersten Textraster vorkommt. Wie groß ist diese? Und jetzt kannst du dir überlegen, was passiert, wenn \(n\) gegen unendlich geht, was dann die Wahrscheinlichkeit ergibt, dass der gesuchte Text in keinem der Textraster vorkommt. Wie groß ist diese? Und wie groß ist dann die W'kt, dass der Text an mindestens einer Rasterstelle stehen muss?
Gruß
Bozzo
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
