12: Frosch und Kröte / Frog and Toad

  • n9 = 14 und nicht 13, siehe Catalan-Zahlen.

    Dann stimmen deine px mit meinen überein. Beim Hochziehen scheinst du ein zweites Mal mit nx multipliziert zu haben. Dadurch werden die Werte für steigendes n größer.

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Georg J. aus D. () aus folgendem Grund: Hinweis auf Catalan-Zahlen

  • n9 = 14 und nicht 13, siehe Catalan-Zahlen.

    Dann stimmen deine px mit meinen überein. Beim Hochziehen scheinst du ein zweites Mal mit nx multipliziert zu haben. Dadurch werden die Werte für steigendes n größer.

    Ich habe auch 14 Pfade, die auf X = 9 führen. Allerdings gefällt mir die 6.Catalan- Zahl viel besser (ich hätte das Zeitlimit bei meiner "Eindampfung" doch auf 11 Sekunden legen sollen) ;)

  • Und hier die Formel für die Anzahl der möglichen Wege w:


    z = Betrag der Startzahl, z > 0, in der Aufgabe z = 100.


    n = Sekunden nach Start, n - z gerade und >= 0, nach z Sekunden gibt es erstmals einen und zwar genau einen Weg.



    w = 2z/(n+z) * ( n-1 über (n-z)/2 )

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 8 Mal editiert, zuletzt von Georg J. aus D. () aus folgendem Grund: Formel auf Schrittweite 2 korrigiert. n - z gerade, statt n gerade

  • [...]

    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).

    [...]

    Danke. Genau die Schwierigkeit hier eine geschlossene Formel angeben zu können, hat mich dann auf die Lösung gebracht - hat aber etwas gedauert.


    Das Problem für die Wege eine Formel angeben zu können, ist das die Binominialkoeffizienten nicht gehen, bzw. um Korrekturterme erweitert werden müssen, die zwar mit Hilfe des Pascalschen Dreiecks verständlich und einfach herzuleiten sind, aber eben schwer umsortiert und in einen geschlossenen Ausdruck gebracht werden können.

  • n9 = 14 und nicht 13, siehe Catalan-Zahlen.

    Dann stimmen deine px mit meinen überein. Beim Hochziehen scheinst du ein zweites Mal mit nx multipliziert zu haben. Dadurch werden die Werte für steigendes n größer.

    Stimmt, habe den 14. Pfad übersehen - aber jetzt erwischt :). Sehr hübsch der Zusammenhang mit den Catalan-Zahlen, diese begegnen mir gerade zum ersten Mal!!


    hatte mich in Maple vertippt bei den Übergängen von Pi zu Pi+1

    Nun kann ich die Wahrscheinlichkeiten von Georg aus seinem Beitrag #37 bestätigen. Ich erhalte mit Maple gerundet nun ebenfalls:


    p1= 70,9 %

    p3= 15,8 %

    p5= 7,0 %

    p7= 3,9 %

    p9= 2,4 %


    hier der genaue Rechenweg:

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


    P.S. Sehe gerade, dass du (Georg) eine geschlossene Formel für n(x) vorschlägst. Super. Schaue ich mir nachher mal an!

  • Nachtrag zu den Catalanzahlen:
    Habe mit Maple gerade die Quotientenfolge Cn+1 / Cn untersucht. Nette Eigenschaft: streng monoton wachsend, Grenzwert: 4


    Das bedeutet, dass für die eben betrachtete Vereinfachung (Mathe Jürgen: Start bei +/- 1 ) px für alle Zeitpunkte (auch > 10) tatsächlich monoton fallend ist!

    Es gilt ja (siehe Formel im Beitrag oben (Link)):


    pi+1 = ( Cn+1 / Cn ) * 2/9 * pi


    Aber mit der oben beschriebenen Eigenschaft gilt: ( Cn+1 / Cn ) * 2/9 < 1 ( da Cn+1 / Cn < 9/2=4,5)


    Anders ist es bei der Originalaufgabe: Da haben wir ein Maximum nach 5 Minuten 48 Sekunden (288 Sek).
    Liegt daran, dass n(x) zunächst viel stärker wächst, als die Catalanfolge... bin mal gespannt, ob die geschlossene Formel von Georg passt.
    Hättest du da eine grobe Herleitungsskizze/ Gedankengänge? Hast Du da auch die Catalanzahlen miteinbezogen?

  • ... bin mal gespannt, ob die geschlossene Formel von Georg passt.

    Hättest du da eine grobe Herleitungsskizze/ Gedankengänge? Hast Du da auch die Catalanzahlen miteinbezogen?

    Ich hatte für z = 1 und meine abbrechenden Pascalschen Dreiecke mit z = 10 schon die Anfangswerte. Damit (siehe Links) fand ich die z-spezifischen Formeln mit Binomialkoeffizienten (in den Links als C(n,k)), die ich dann verallgemeinert habe. Dabei hatte ich zuerst für n eine Schrittweite von 1 statt 2, was mir zum Glück noch selbst auffiel.

  • Eine geschlossene Formel für das n(x) wäre wohl (ähnlich zu der von Georg J. aus D., vielleicht minimal einfacher)


    n(x) = 100/x * [x über (x-100)/2]


    Die [x über (x-100)/2] sind ähnlich wie in pierrots Herleitung einfach die Anzahl der Wege, die nach x Sekunden die 0 erreichen, aber nicht notwendigerweise zum ersten Mal (aus x Sprüngen wird (x-100)/2 mal nach rechts und (x+100)/2 mal nach links gesprungen).


    Dieser Ausdruck ist zu hoch, da wir ja nur die Wege betrachten wollen, bei denen nach x Sekunden zum ersten Mal die 0 erreicht wird.

    Es fehlt also noch ein Korrekturfaktor: Nämlich die bedingte Wahrscheinlichkeit -- unter der Bedingung, dass nach x Sekunden die 0 erreicht wird -- dass die 0 dann zum ersten Mal (und nicht vorher schon) erreicht wird.


    Und diese bedingte Wahrscheinlichkeit ist genau 100/x.

    Mit pierrots erstem Ansatz überschätzt man also die wahre Anzahl um den Faktor x/100.

  • Nach sehr lehrreicher Beschäftigung mit den vereinfachten Aufgabenstellungen möchte ich noch mal zu der ursprünglichen Aufgabenstellung etwas sagen.


    In der Aufgabenstellung ist bei mir Lösung 9 "Es gilt 0,256 < p ≤ 0,512" grün hinterlegt.


    Inzwischen bin ich soweit, das für falsch zu halten.


    Meine Überlegung dazu ist die folgende:

    Zunächst einmal ist aufgrund ihrer beider Linkslastigkeit für Frosch Friedolin genauso schwer, die Null zu meiden,

    wie es für Kröte Kriemhilde schwer ist, sie zu erreichen. Diese Symmetrie zu entdecken war die erste Hürde.

    Wenn Kriemhilde nun zu irgendeinem Zeitpunkt 8 Uhr + (100+2i) s die Null erreicht,

    wird sich Friedolin noch rechts von der Null aufhalten, denn er soll die Null ja gemäß Aufgabenstellung erst nach Kriemhilde erreichen.

    Aufgrund seiner Linkslastigkeit wird er dann aber, mit einiger SEHR wenigen Ausnahmen,

    bei denen er doch nicht mehr rechtzeitig zurück zur Null kommt, die Null in den meisten Fällen erreichen.


    Demnach wäre die korrekte Lösung Lösung 10, da p=1. (bzw. 1-epsilon)

  • Dass Fridolin die Null meiden und erst nach Kriemhilde ankommen soll, steht so nicht in der Aufgabe. Es ist die Wahrscheinlichkeit dafür gesucht, dass er nach ihr ankommt. Wenn p=1 richtig wäre, müsste er garantiert nach ihr ankommen, was sicherlich nicht der Fall ist.

  • Dass Fridolin die Null meiden und erst nach Kriemhilde ankommen soll, steht so nicht in der Aufgabe. Es ist die Wahrscheinlichkeit dafür gesucht, dass er nach ihr ankommt. Wenn p=1 richtig wäre, müsste er garantiert nach ihr ankommen, was sicherlich nicht der Fall ist.

    Exakt.


    Gefragt war nach der WS das F nach K ankommt

    unter der Bedingung, dass beide ankommen und beide mit der gleichen Zeit-Verteilung die 0 erreichen,

    nur halt mit unterschiedlicher WS (Faktor 2^100).

    Die gesamte Komplexität durch die Wege und WS / Linkslastigkeit ihrer Sprünge diente eigentlich nur zur Ablenkung von dieser einfachen Fragestellung.

    Ich habe einige Zeit gebraucht, um zu bemerken, dass das Ankommen eine echte Bedingung der Lösung ist und die Komplexität der Aufgabe in sich zusammenstürzen lässt.


    Für jeden gegebenen Zeitpunkt xiK = 100sec + 2 i sec; 0 <= i < 28750 des Ankommens von K mussten die relative (auf das Intervall von 8:00 bis 24:00 Uhr normierte) Wahrscheinlichkeiten WjFrel des späteren Ankommens xjF = 100sec + 2 j sec; i < j < 28750 von F aufsummiert werden ( => SiF = Sum(j=i+1, j<28750, j++){WjFrel} ) und diese Summe mit der ebenfalls relativen (auf das Intervall von 8:00 bis 24:00 Uhr normierten) Wahrscheinlichkeit WiKrel für das Ankommen von K zum Zeitpunkt xiK gewichtet werden (bedingte Wahrscheinlichkeiten). Die Summe dieser gewichteten Summen ist die gesuchte Wahrscheinlichkeit ( => WS = Sum(i=0, i<28750, i++){WiKrel x SiF} ).


    Da die Zeit-Verteilung des Ankommens für F und K identisch ist und da sowohl F als auch K garantiert ankommen, ist die relative Wahrscheinlichkeit für beide gleich. Der Faktor 2^100 fällt durch diese Normierung (die durch das garantierte Ankommen gegeben ist) raus: WiFrel = WiKrel = Wi,rel


    Dennoch fand ich es dann doch extrem interessant, zu sehen, dass die Summe über i der mit Wi,rel gewichteten Summen über Wj,rel ; i < j < 28750 gleich groß ist, wie deren Gegenteil. Insbesondere da die Summe der Wege und damit die Wahrscheinlichkeit für F anzukommen (Sum{Wi,rel}) doch recht schnell konvergiert und die Zeit-Verteilung des Ankommens ihr Maximum bei recht kleinen i hat.

    Dies hatte ich dann tatsächlich erst im Nachhinein wirklich verstanden. In meiner abgegebenen Lösung hatte ich diese doppelte Summe falsch abgeschätzt, da ich versäumt hatte die Aufgabe mit deutlich kleineren Zahlen einfach mal auszurechnen.

  • Dass Fridolin die Null meiden und erst nach Kriemhilde ankommen soll, steht so nicht in der Aufgabe. Es ist die Wahrscheinlichkeit dafür gesucht, dass er nach ihr ankommt. Wenn p=1 richtig wäre, müsste er garantiert nach ihr ankommen, was sicherlich nicht der Fall ist.

    "meiden"

    M.E. ist es ist für die Mathematik unerheblich, ob Wahrscheinlichkeitsfrosch Fridolins Pfade zufallsbedingt, göttliche Fügung oder Ergebnis einer bewussten Entscheidung sind, sofern sie den gegebenen Wahrscheinlichkeiten 2:1 für links:rechts genügen.

    Aufgabe schrieb: "Fridolin springt lieber nach links (zu den kleineren Zahlen) als nach rechts (zu den größeren Zahlen): Mit Wahrscheinlichkeit 1/3 springt er jeweils von seiner momentanen Position f nach f+1, mit Wahrscheinlichkeit 2/3 springt er nach f-1."


    Dennoch lässt mich dieser Kommentar aus der Moderatorenecke innehalten.


    Wenn Gesamtwahrscheinlichkeiten gefragt sind, dann ist nach kurzer Rechnung offensichtlich, dass Fridolin in der großen Mehrzahl der Fälle vor Kriemhilde bei der Null ankommt. Bei dieser Betrachtung wäre das gesuchte p nahezu 0, (bzw. p< 0,002; Lösung 1), weil Fridolin gemessen an seinen Ankünften nur äußerst selten nach Kriemhilde ankommt.


    Wenn die bedingte Wahrscheinlichkeit gefragt ist, auf die ich erst durch Lektüre der Forumsbeiträge #13 und #24 aufmerksam geworden bin, dann finde ich meine Behauptung aus #51 immer noch sehr naheliegend: Sofern Kriemhilde die Null vor Fridolin erreicht, wird Fridolin die Null mit nahezu 100% Wahrscheinlichkeit am gleichen Tag erreichen.


    Allerdings ist die vielfach bemerkte Symmetrie vielleicht doch ab einem bestimmten Zeitpunkt nicht mehr gegeben.


    Krimhilde verläuft sich im Laufe des Tages immer mehr in die hohen negativen Zahlen. Jede Sekunde verlagert sich die Position an der sie zu erwarten wäre um -1/3. Deshalb sind ihre Chancen, die Null überhaupt zu errreichen anfangs tendentiell höher als später. Ihre "Schwerpunktposition" nach 5 Minuten, also nach 300 Sekunden ist dann fast bei -200. (Da die wenigen Pfade, die die Null erreichen, ihren Schwerpunkt nicht mehr um -1/3 pro Sekunde verschieben, sinkt die allgemeine Driftgeschwindigkeit Kriemhildes mit der Zeit minimal.) Die Wahrscheinlichkeit von -200 aus die Null zu erreichen, wird vermutlich dem Quadrat der ohnehin geringen Wahrscheinlichkeit, die Null von -100 aus zu erreichen, entsprechen.
    Die folgende Zeitreihe verdeutlicht, wie die Wahrscheinlichkeit für Kriemhilde, die Null zu erreichen, mit der Zeit sinkt. Dazu betrachtet man z.B. die Position "-98" zu den Zeitpunkten 2 s, 4 s und 6 s: von zunächst 1/9 = 81/729 über 8/81 = 72/729 auf 60/729 schwächt sich der Strom, der "Nullgänger" im 2-Sekundentakt ab. Aber nichts desto trotz ist ein stetes Nachströmen gewährleistet.

    ZeitPos-106-105-104-103-102-101-100-99-98-97-96
    0-1001
    1-100 1/3
    2/31/3
    2-100 2/3
    4/94/91/9
    3-101
    8/2712/276/271/27
    4-101 1/3
    16/8132/8124/818/811/81
    5-101 2/3
    32/24380/24380/24340/24310/2431/243
    6-10264/729192/729240/729160/72960/72912/7291/729



    Für Fridolin sieht es anders aus. Seine "Erwartungsposition" driftet ebenfalls pro Sekunde -1/3 nach links. So werden bereits ab t=100 die ersten Pfade bei Null beendet. Aus diesen Pfaden generieren sich keinerlei Pfadverlängerungen mehr. Die "Pfade- verschluckende-Null" bewirkt, dass zu einem späteren Zeitpunkt doch keine Symmetrie zwischen Fridolin rechts von der Null und Kriemhilde links von der Null vorliegt, weil durch Fridolins Linksdrift ständig große Anteile von seinen noch existenten Pfaden in der Null beendet werden, während von Kriemhildes Seite der geringe Strom an Pfaden in oben beschriebener Weise zwar kontinuierlich abnimmt aber eben in deutlich geringerem Maße durch die Null beendet wird.


    Vielleicht hätte ich es bei meinem frühen post #7 belassen und meiner Rechenlösung mit p=1/3 vertrauen glauben sollen, denn lösen kann ich es immer noch nicht. Deshalb warte ich jetzt tatsächlich auf die Musterlösung und hoffe, diese bestenfalls verstehen oder zumindest akzeptieren zu können. :)

  • Sofern Kriemhilde die Null vor Fridolin erreicht, wird Fridolin die Null mit nahezu 100% Wahrscheinlichkeit am gleichen Tag erreichen.

    Das ist sicherlich richtig, ist aber nicht gefragt, denn dass sowohl Fridolin als auch Kriemhilde die Null erreichen, ist ja bereits vorgegeben.



    Krimhilde verläuft sich im Laufe des Tages immer mehr in die hohen negativen Zahlen. Jede Sekunde verlagert sich die Position an der sie zu erwarten wäre um -1/3. Deshalb sind ihre Chancen, die Null überhaupt zu errreichen anfangs tendentiell höher als später

    Auch das ist völlig korrekt, für Fridolin ist aber ebenfalls die Wahrscheinlichkeit höher, die Null recht früh zu erreichen. Die höchste Wahrscheinlichkeit hat jeder für sich auch noch exakt zum selben Zeitpunkt, wenn auch Fridolins Wahrschheinlichkeit wesentlich höher ist.


    Um das Ziel nach i Sprüngen zu erreichen, muss ein Tier (100 + (i-100)/2) mal in Richtung Ziel gesprungen sein und ((i-100)/2) mal vom Ziel weg. Wenn man jetzt n als Anzahl der Varianten nimmt, in denen das möglich ist (das ist ja für F und K gleich, hat ja nichts mit der Wahrscheinlichkeit für die eine oder andere Richtung zu tun), ergibt sich für die Wahrscheinlichkeit, exakt nach i Sprüngen das Ziel zu erreichen, folgendes:

    n*(pHin)100*(pHin*pWeg)(i-100)/2

    Nachdem sowohl n als auch das Produkt aus pHin und pWeg für beide Tiere identisch ist, der Faktor pHin100 aber unabhängig von i ist, steht dann in der Tabelle der Ankunftswahrscheinlichkeiten zu einem bestimmten Zeitpunkt in jeder Zeile in beiden Spalten ein Wert, der sich um einen konstanten Faktor (1/3)100*(2/3)100
    =(2/9)100 voneinander unterscheidet.


    Und genau da kommt jetzt die Aussage ins Spiel, dass beide im Laufe des Tages die Null erreichen. Vielleicht zur Veranschaulichung ein einfaches Zahlenbeispiel:

    Gehen wir von einer Zieleinlaufwahrscheinlichkeit wie folgt aus:

    ZeitFridolinKriemhilde
    10,010,001
    20,020,002
    30,040,004
    40,030,003


    Dann würde Fridolin mit 10% Wahrscheinlichkeit das Ziel in den ersten 4 Schritten erreichen, Kriemhilde nur mit 1% Wahrscheinlichkeit, zu jedem Zeitpunkt ist die Wahrscheinlichkeit für Fridolin um einen konstanten Faktor (hier 10) höher als für Kriemhilde. Wenn nun aber vorgegeben ist, dass beide das Ziel innerhalb dieser 4 Schritte erreichen, müssen die Wahrscheinlichkeiten dieser 4 Schritte auf insgesamt 100% skaliert werden (denn wir wissen ja sicher, dass einer dieser Fälle eintritt).

    Daher müssen wir in der Fridolin-Spalte jeden Wert mit 100/10 und in der Kriemhilde-Spalte jeden Wert mit 100/1 multiplizieren, und - oh Wunder - in beiden Spalten stehen plötzlich genau dieselben Werte, und damit ist die bedingte Wahrscheinlichkeit, dass F oder K das Ziel zu einem bestimmten Zeitpunkt (oder auch bis zu einem bestimmten Zeitpunkt) erreichen, exakt gleich (nämlich p1=10%, p2=20%, p3=40% und p4=30%).

    Und was ist nun die Wahrscheinlichkeit, dass F nach K ankommt?


    Summe über alle pi * (Summe aller pj für j > i)/(Summe aller pj für j <> i) für i = 1..4


    p1*(p2+p3+p4)/(p2+p3+p4)+p2*(p3+p4)/(p1+p3+p4)+p3*(p4)/(p1+p2+p4)+p4*(0)/(p1+p2+p3)=

    =10%*90%/90%+20%*70%/80%+40%*30%/60%+30%*0/70%=10%+17,5%+20%=47,5%


    Und je mehr Zeilen es gibt und je kleiner die Einzelwahrscheinlichkeiten sind, desto mehr nähert sich diese Summe der 50% an (da der rauszurechnende Anteil für die gleichzeitige Ankunft immer kleiner wird).


    Wobei ich im Moment nicht ganz verstehe, wie da überhaupt etwas ungleich 50% rauskommen kann, denn nachdem alle Zeilen in der Tabelle der bedingten Wahrscheinlichkeiten zwei gleiche Werte enthalten, ist ja die Wahrscheinlichkeit für F kommt nach K an zwingend genau gleich, wie K kommt nach F an. Insofern kann das ja nichts anderes als 50% ergeben...

  • Auch wenn meine Simulation 0.5 sagt wäre meine Intuition auch 1/3 :)
    Zum Glück ist beides in einem Intervall, dann musste ich mich nicht entscheiden

    Warum wäre Deine Intuition 1/3?

    K und F müssen doch jeweils 2 Sprünge machen, um von einer Position bei der sie die 0 "verfehlt" haben wieder zur 0 zu kommen.

    Also ich hätte dann eher die Intuiition von 1/9, was aber genauso falsch ist,

  • Ich komme auf andere Wahrscheinlichkeiten:

    ZeitF vor KF und K gleichzeitigF nach K
    19 %1 %0 %
    214 %4 %2 %
    312 %16 %12 %
    40 %9 %21 %
    Summe35 %30 %35 %


    Die letzte Zeile enthält die Summe.

    F vor K mit 35 % gleich F nach K mit 35 % => 0,5

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 2 Mal editiert, zuletzt von Georg J. aus D. () aus folgendem Grund: Spalte "Zeit" eingefügt.

  • Ich komme auf andere Wahrscheinlichkeiten:


    Nachdem deine Tabelle nicht beschriftet ist, hab ich ein wenig gebraucht, um nachzuvollziehen, was du da auflistest. Wenn ich das richtig verstehe, ist jede Zeile bezogen auf eine bestimmte Ankunftszeit von Fridolin, richtig?

    Okay, ich glaube, jetzt hab ich auch meinen Fehler gefunden, ich habe im Prinzip aus zwei Urnen mit je 10 Kugeln gezogen (beschriftet mit 1x1, 2x2, 4x3 und 3x4), und um die Bedingung der Aufgabenstellung zu erfüllen, dass Fridolin und Kriemhilde nicht gleichzeitig ankommen dürfen, habe ich nach der Ziehung der Kugel aus K die entsprechenden Kugeln aus F entfernt, bevor ich hier ziehe, und da ist wohl der Haken, ich darf nach der Ziehung aus der einen Urne die andere nicht mehr verändern, weil ich sonst die bedingten Wahrscheinlichkeiten versaue.