12: Frosch und Kröte / Frog and Toad

  • Ich wollte wollte aber nicht nur endlich viele Versuche simulieren um doofe Zufälle auszuschließen.

    Auch wenn ich deinen Lösungsansatz spannend finde und auch gerne einmal ausprobieren würde, muss ich diesem Zitat hier widersprechen. Doofe Zufälle schließt man bei der Simulation mit Hilfe des Gesetz der großen Zahlen aus. Wenn ich mit jedem Programmdurchlauf 10000 Versuche simmuliere und insgesamt 10 mal das Programm starte und jedes Mal kommt etwas im Bereich 0,49 - 0,51 raus, dann kann ich mit sehr sehr sehr hoher Wahrscheinlichkeit ausschließen, dass die richtige Lösung eigentlich 0,4 wäre und hier nur ein "doofer Zufall" vorliegt.


    Mich würde außerdem mal interessieren, ob du auch +100 und -100 als Startpunkte in deinem Programm verwendet hast... weil die Wahrscheinlichkeiten, dass Kriemhilde da ihr Ziel erreicht müsste so winzig sein, dass der Computer irgendwann auf 0 rundet (würde ich behaupten - hängt natürlich auch von der Programmiersprache ab). Code interessiert mich also auch ;)

  • Natürlich hast du Recht, aber ich bin irgendwie nicht der Fan von Aussagen wie "Die Wahrscheinlichkeit grenzt an 1 und darum stimmt es".

    Sowas mach ich nur wenn mir gar nichts besseres einfällt. Ist einfach ne persönliche Ansicht😅

    Ja, ich bin von -100 und 100 gestartet.

    Und ja, die Wahrscheinlichkeit dass K in Runde n ankommt ist für alle n mickrig. Daher wahrscheinlich auch der Rundungsfehler auf 0.51, aber wenn man mit doubles arbeitet wird zumindest nicht auf 0 gerundet.

    Sprache ist übrigens python3

  • Ich habe - nachdem ich die Symmetrieüberlegung gemacht hatte und auf die Lösung gekommen war - nochmal nachprogrammiert, wie die Wahrscheinlichkeiten sind, dass Fridolin bzw. Kriemhild zu welchem Zeitpunkt bei 0 ankommen. Mich hat auch interessiert, ob man die Symmetrie sieht, oder ob die Zahlen zu klein werden.


    Es ist aber so, dass es auch bei Kriemhild noch "groß genuge" Anteile gibt, so dass die Ungenauigkeiten durch die Anteile, die "weggenullt" werden, nicht relevant sind.


    Durch die anderen Faktoren gibt es eigentlich keine Ungenauigkeiten, denn die Pfade von Kriemhild, die zur 0 führen, sind ja genau um den Faktor 2 ^ 100 kleiner als die gespiegelten Pfade von Fridolin, und dieser Faktor (2 ^ 100) ist exakt darstellbar (bei den "normalen floats").


    Die Laufzeit des Programms waren auf meinem Rechner weniger als 10 Sekunden.



    Interessant finde ich, dass die Wahrscheinlichkeit, bei 0 anzukommen, zum Zeitpunkt 288 am größten ist.


    Das Programm findet nicht nur heraus, dass die Wahrscheinlichkeiten für Kriemhild und Fridolin, zu einem bestmmten Zeitpunkt anzukommen, gleich sind (vorausgesetzt, dass sie überhaupt ankommen). Aus der Symmetrie ergibt sich dann sofort, dass die gesuchte Wahrscheinlichkeit 1/2 ist.
    Außerdem rechnet es noch die Gewinnwahrscheinlichkeiten aus, dass Fridolin bzw. Kriemhild gewinnen, unter der Voraussetzung, dass beide bei der 0 ankommen.

    Die Wahrscheinlichkeiten sind identisch, aber nicht 1/2, weil das "Unentschieden" nicht wegnormiert ist.



  • Interessant finde ich, dass die Wahrscheinlichkeit, bei 0 anzukommen, zum Zeitpunkt 288 am größten ist...


    fast... ich kam rechnerisch auf 290 Sekunden (siehe Beitrag 1, da hatte ich die Lösung + Rechnung bereits gepostet...)


    Hier nochmal der rechnerische Weg (unter Zusatz, ganz unten, zunächst beschreibe ich n(x): wie viele verschiedene Pfade gibt es auf die Null (das ist ja gerade symmetrisch bei den beiden), dann habe ich die Verteilung angegeben, Maximum nach 290 Sekunden:


    https://www.dropbox.com/s/nprc…12_Frosch_Kroete.JPG?dl=0

  • Ups, das hatte ich übersehen.

    Stimmt aber nicht mit meinen numerischen Ergebnissen überein. Ich zweifle an n(x). Kannst du bitte erklären, wie n(x) nur Wege erfasst, die nur ganz am Schluss die Null erreichen - und gleichzeitig alle solchen Wege erreicht? Mir scheint die Formel zu einfach, aber vielleicht ist sie auch genial :-)

  • Ich zweifle an n(x). Kannst du bitte erklären, wie n(x) nur Wege erfasst, die nur ganz am Schluss die Null erreichen - und gleichzeitig alle solchen Wege erreicht? Mir scheint die Formel zu einfach, aber vielleicht ist sie auch genial :-)

    Aber sehr gerne doch, auf meinem Lösungsblatt war unten nur noch recht wenig Platz. Da die Formel für n(x) (Anzahl der verschiedenen Wege nach x Sekunden auf die Null zu springen) für die Aufgabenlösung völlig irrelevant ist (ist ja für F und K genau gleich, daher die Symmetrie -> sprich die Gleichverteilung schlussendlich),
    habe ich die Formel für n(x) am Ende des Blattes nur recht kurz erläutert (Unter Zusatz).


    Ich habe das jetzt mal ausführlicher dargestellt (siehe Link zwei Zeilen tiefer) - sollte jetzt klar sein ":::" oder? Nett von Dir einen "Blumenstrauß" in Aussicht zu stellen. Aber diese eher schlichte Herleitung hat das Prädikat "genial" wohl nicht verdient ;).
    https://www.dropbox.com/s/kc6f…12_Herleitung_nx.JPG?dl=0



    Hier noch einmal das ursprüngliche Lösungsblatt (n(x) wird unten unter "Zusatz" aufgeführt):

    https://www.dropbox.com/s/cfbtd9grig96cwf/12_Frosch_Kroete.JPG?dl=0


    Schaut man sich die stetige Verteilung an, so liegt das Maximum fast exakt in der Mitte von 288 (deine Lösung) und 290 Sekunden (meine Lösung),

    aber eben etwas näher an 290: Siehe: Maple-Plot: (daher schrieb ich auch "fast", der Unterscheid: 288 bzw 290 ist marginal!!). OK?

    https://www.dropbox.com/s/7rsi…/12_Plot_Maximum.png?dl=0

  • Ich glaube, dass du da auch Pfade mitzählst, die schon früher auf die 0 kommen. Zum Beispiel bei n = 104 den Pfad, der erst 100 mal nach links geht, dann zweimal nach rechts und dann wieder zweimal nach links.

    Ja, das meinte ich. Dementsprechend ist auch n(104) = 5151 > 5150 (Anzahl der Pfade, die mein Programm mit entsprechender Modifikation berechnet).


    Die (numerische) Summe von Pierrots Wahrscheinlichkeiten ist schon für die 100 <= x < 1000 größer als 1: 1.3333333333333177. (Falls ich mich nicht verrechnet habe...)

  • Ja, das meinte ich. Dementsprechend ist auch n(104) = 5151 > 5150 (Anzahl der Pfade, die mein Programm mit entsprechender Modifikation berechnet).

    fürwahr, das stimmt: ab x>=104 zähle ich tatsächlich zu viele pfade: für x=104 einen einzigen zu viel, dann werden es ein paar wenige mehr, daher komme ich auf ein minimal anderes Ergebnis! Jetzt würde mich dennoch interessieren „:::“ welchen quantitativen Unterschied dein Programm zwischen 288 und 290 Sekunden ausspuckt.

  • fürwahr, das stimmt: ab x>=104 zähle ich tatsächlich zu viele pfade: für x=104 einen einzigen zu viel, dann werden es ein paar wenige mehr, daher komme ich auf ein minimal anderes Ergebnis! Jetzt würde mich dennoch interessieren „:::“ welchen quantitativen Unterschied dein Programm zwischen 288 und 290 Sekunden ausspuckt.

    Der Unterschied ist nicht groß, aber vorhanden. Gezeigt werden die Wahrscheinlichkeiten für Fridolin, ohne weitere Bedingungen, dass zum Zeitpunkt x die Null zum ersten Mal erreicht wird. (Hoffentlich habe ich pierrots Formeln richtig umgesetzt.)


    x:::pierrot
    2880.016853245981613647
    0.02198673296319125
    2900.01682686303243865
    0.02202630548502301
  • Merci ":::" - allerdings meinte ich eigentlich, dass mich interessiert, was bei DEINEM numerischen Ansatz konkret für die Wahrscheinlichkeiten nach 288 und 290 Sekunden herauskommt, sollte auch sehr nah beieinander liegen.


    Nachtrag zu n(x): meine Formel ist wie richtig bemerkt nur für die ersten Werte von x korrekt, ab x=104 zähle ich zu viele Pfade: Zunächst nur einen zuviel. Die Anzahl der zu viel gezählten Pfade wächst aber mit wachsendem x erheblich. Am Ende: x= 57 600 - sind unter meinen gezählten Pfaden die allerwenigsten valide, ist doch dann die Wahrscheinlickeit, bei einem meiner gezählten Pfade vorher auf die Null zu springen, dann riesig.


    Interessant ist, dass dieser "Fehler" für große x in der Formel für n(x) kaum Gewicht hat: Die Verteilungskurve ist im Verlauf schon ganz gut angenähert.
    Insbesondere, was die Maximumsstelle angeht (numerische Lösung von ":::" und die meinige liegen ja kaum auseinander: 288-290).


    Schaut man die Verteilungsfunktion P_x (in meinem ersten Lösungsblatt) an, wird auch klar warum:
    a) Exponentialfunktion (2/9)^n dominiert natürlich für große n (daher geht die Wahrscheinlichkeit dann schnell gegen Null), der Fehler in n(x) spielt dann kaum mehr eine Rolle
    b) n(x) tritt natürlich sowohl im Nenner als auch um Zähler aus - "kürzt sich sozusagen etwas raus" (Durch den Nenner zieht man die Wahrscheinlichkeit im Tagesbereich auf 100%, weiß man doch, dass beide sicher ankommen).


    Auch wenn für die Lösung der Aufgabe völlig irrelevant, wäre es natürlich noch interessant eine korrekte geschlossene Formel für n(x): Anzahl der Pfade (verschiedene Wege) zum Zeitpunkt x auf die Null (zum ersten Mal!) zu finden. So ganz trivial wie in meinem ersten Schnellschuss ist das tatsächlich nicht. Vlt hat ja jemand Lust und die Zeit (bei mir hapert s eher an letzterem), sich damit zu befassen.


    Warum diese super Aufgabe auf den letzten Platz gewählt wurde, ist mir unklar. Das hat sie DEFINITIV nicht verdient, gehört in meinen Augen zu den "Top VIER"! :thumbsup:

    Vlt lag es auch daran, dass einige ohne Ansatz zu lange im Nebel umherstocherten???

  • Dank der regen Diskussion über Aufgabe 12 glaube ich, dass so langsam auch bei mir der "Groschen" (endlich) gefallen ist.

    Mein Hauptproblem war, dass ich stundenlang Wahrscheinlichkeiten von Pfaden berechnet habe (was von Hand ganz schön zeitintensiv war ;)), obwohl man das gar nicht muss. Im Nachhinein betrachtet macht es wenig Sinn Wahrscheinlichkeiten von Ereignissen zu berechnen, die schon garantiert eingetreten sind. Laut Text sind sowohl Fridolin als auch Kriemhilde im Zeitlimit angekommen.

    Also schreibe ich die Ankunftszeiten t von F und K jeweils auf, wobei gilt 100 <= t <= 57600.

    Um meine Überlegung besser aufschreiben zu können "dampfe" ich das Problem mal etwas ein. Die beiden starten auf + 1 bzw. - 1 und das Zeitlimit beträgt 10 Sekunden. Somit sind folgende Ankunftszeiten möglich: 1 ; 3 ; 5 ; 7 ; 9

    Jetzt simuliere ich das ganze mit einem Urnenexperiment: Jede Ankunftszeit wird jeweils auf eine Kugel geschrieben und die fünf Kugeln werden in die Urne gelegt. aus dieser Urne zieht Kriemhilde und Fridolin jeweils eine Kugel. Damit die beiden nicht die gleiche Ankunftszeit ziehen, wird ohne Zurücklegen gezogen.

    Wer von beiden beginnt ist egal, sagen wir einmal Kriemhilde beginnt. Jede der fünf Kugeln wird von K mit einer Wahrsch. von 1/5 gezogen.


    Kriemhilde zieht Wahrscheinlichkeit, dass K vor F ankommt Wahrscheinlichkeit, dass K nach F ankommt

    1 1/5 * 1 = 1/5 = 4/20 1/5 * 0 = 0

    3 1/5 * 3/4 = 3/20 1/5 * 1/4 = 1/20

    5 1/5 * 2/4 = 2/20 1/5 * 2/4 = 2/20

    7 1/5 * 1/4 = 1/20 1/5 * 3/4 = 3/20

    9 1/5 * 0 = 0 1/5 * 1 = 1/5 = 4/20


    Das Problem ist demnach völlig symmetrisch bezgl. der Wahrscheinlichkeiten. Es gilt p(K vor F) = ( 4 + 3 + 2 + 1 + 0 )/20 = 10/20 = 0,5 :)

    Dass beim eigentlichen Experiment 28 751 "Kugeln" in der Urne liegen ändert die Symmetrie nicht.

  • Du solltest selbst formatierte Tabellen

    in Code-Tags einschließen:

    Code
    1. Kriemhilde zieht Wahrscheinlichkeit, dass K vor F ankommt Wahrscheinlichkeit, dass K nach F ankommt
    2. 1 1/5 * 1 = 1/5 = 4/20 1/5 * 0 = 0
    3. 3 1/5 * 3/4 = 3/20 1/5 * 1/4 = 1/20
    4. 5 1/5 * 2/4 = 2/20 1/5 * 2/4 = 2/20
    5. 7 1/5 * 1/4 = 1/20 1/5 * 3/4 = 3/20
    6. 9 1/5 * 0 = 0 1/5 * 1 = 1/5 = 4/20
  • Wer von beiden beginnt ist egal, sagen wir einmal Kriemhilde beginnt. Jede der fünf Kugeln wird von K mit einer Wahrsch. von 1/5 gezogen.

    Das bildet aber nicht die unterschiedlichen Wahrscheinlichkeiten ab, nach genau x Sekunden die Null zu erreichen. Mit deinem Zahlenbeispiel müssten die Wahrscheinlichkeiten für die Kugeln (erste Spalte (Nummerierung))

    Code
    1. 0,709220625
    2. 0,157604583
    3. 0,070046481
    4. 0,038914712
    5. 0,024213599

    sein. Das ändert aber nichts an der Symmetrie zwischen F und K.


    Seien x und y 2 aus 5 Kugeln: 5 * 4 = 20 Paare (x, y),

    10 aufsteigend x < y

    und 10 absteigend x > y.


    Die Wahrscheinlichkeit für (x, y) ist gleich der Wahrscheinlichkeit für (y, x).


    Daraus folgt p(K vor F) = p(F vor K).


  • Ich hadere immer noch mit dieser Kröten-Frosch-Aufgabe!

    Wie müsste denn diese kleine übersichtliche Tabelle oben aussehen,

    wenn man die für diesen Fall tatsächlichen Wahrscheinlichkeiten berücksichtigt, die Georg J. aus D. errechnete?


    Das bildet aber nicht die unterschiedlichen Wahrscheinlichkeiten ab, nach genau x Sekunden die Null zu erreichen. Mit deinem Zahlenbeispiel müssten die Wahrscheinlichkeiten für die Kugeln (erste Spalte (Nummerierung))

    Code
    1. 0,709220625
    2. 0,157604583
    3. 0,070046481
    4. 0,038914712
    5. 0,024213599

    sein.


    Ändert sich da denn nicht auch was bei 1/4; 2/4; 3/4 und beeinflusst die Symmetrie doch?

  • Der Unterschied ist nicht groß, aber vorhanden. Gezeigt werden die Wahrscheinlichkeiten für Fridolin, ohne weitere Bedingungen, dass zum Zeitpunkt x die Null zum ersten Mal erreicht wird. (Hoffentlich habe ich pierrots Formeln richtig umgesetzt.)


    x:::pierrot
    2880.016853245981613647
    0.02198673296319125
    2900.01682686303243865
    0.02202630548502301

    An dieser Formel habe ich mir auch die Zähne ausgebissen. Gibt es dafür einen geschlossenen mathematischen Ausdruck, oder geht es nur numerisch?

  • geschlossene Formel:


    Ich versuche anhand der Vereinfachung von Mathe-Jürgen (Start bei +/- 1, beide kommen innerhalb der ersten 10 Sekunden sicher an) die Symmetrie/ Gleichverteilung (Hochziehen auf 100 Prozent) noch einmal ausführlich zu erläutern (bin immer noch Freund von Stift und Papier, daher Foto unten ;-) ).


    ich komme allerdings auf andere W-keiten nach x=1,3,5,7,9 Sekunden zum ersten Mal auf die Null zu springen als z.B. Georg J. aus D.

    Nachwievor habe ich keine geschlossene Formel für n(x): Anzahl der verschiedenen Pfade nach x Sek. zum ersten Mal auf die Null zu springen. Für die Lösung von A12 ist der konkrete Wert von n(x) wie gesagt unbedeutend, da ja für K und F gleich! (Symmetrie). Will man aber konkrete Wahrscheinlickeiten bestimmen, braucht man n(x) (war aber eigentlich nicht verlangt).


    Der Rest der Formel ist aber eindeutig und auch recht einfach (Mache das lieber per Formel als mit numerischer Programmierung!):


    Falls ich mich bei n(x) nicht verzählt habe (findet denn jemand eine geschlossene Formel?) ergeben sich folgende gerundete W-keiten:
    p1= 57,2 %
    p3= 12,7 %
    p5= 5,7 %

    p7= 6,3 %

    p9= 18,1 %


    Also Minimum für x=5, liegt daran, dass n(x) für x>5 schnell wächst. Der Faktor 2/9 gleicht das zunächst nicht aus (später natürlich locker, aber x<10 nach Voraussetzung!).


    Hier die ausführliche (hoffentlich jetzt verständlichere??) Rechnung am vereinfachten Fall:

    https://www.dropbox.com/s/zonq…/A12_vereinfacht.JPG?dl=0

  • Vielleicht sollte man noch dazuschreiben (obwohl das ja schon vielfach an anderen Stellen steht) dass Kriemhilde und Fridolin die gleichen Wahrscheinlichkeiten haben für die Ankunftszeiten 1 ; 3 ; 5 ; 7 ; 9. Denn wenn Fridolin eine höhere relative Wahrscheinlichkeit für die Ankunftszeit 1 hätte als Kriemhilde, dann würde deine Urnensimulation nicht stimmen.