Aus Symmetriegründen hängt die Wahrscheinlichkeit, von einer Lichtung zurück zum Eingang zu finden, lediglich von der Entfernung zum Eingang ab. Sei $p_i$ die Wahrscheinlichkeit von der Lichtung mit dem Abstand $i$ zum Eingang zurückzufinden. Am Eingang selbst ist Gilfi mit Sicherheit draußen, also ist $p_0=1$.
Die Wanderung von Gimli entspricht mathematisch einer Markow-Kette. An einer Lichtung mit Abstand $i$ gelangt Gimli im nächsten Schritt mit Wahrscheinlichkeit $1/3$ zu einer Lichtung mit Abstand $i-1$, während er mit Wahrscheinlichkeit $2/3$ seinen Abstand auf $i+1$ vergrößert. Im stationären Zustand gilt somit für die Wahrscheinlichkeiten
Ohne auf die Herleitung einzugehen, wissen alte Hasen, dass sich die Lösung dieser Gleichung als Linearkombination aus Exponentialfunktionen schreiben lässt.
Wir wissen, dass $p_0=1$. Ferner können wir fordern, dass die Wahrscheinlichkeit, aus dem Wald herauszukommen im Unendlichen gegen 0 gehen muss. Daher kann der Term mit $a_2=1$ ausgeschlossen werden, d.\,h.\ $c_2=0$. Durch Einsetzen von $i=0$ erhält man danach $c_1=1$. Also gilt
\[
p_i = \left( \frac{1}{2} \right)^i \quad .
\]
Somit ist die Wahrscheinlichkeit, dass Gilmi von einer Lichtung mit Abstand $i=1$ aus dem Wald herausfindet, $p_1=1/2$.
Ich freue mich auch! Wusste, dass es eigentlich über eine Markow-Kette gehen muss, aber als Mathe-Amateur hab ich das bei den entsprechenden Aufgaben noch nie hingekriegt. Lese auch diesmal wieder gerne die Lösungswege von klügeren Leuten, aber wenn sowas nächstes Jahr wieder vorkommt, werde ich mich auch dann wieder durch Fleißarbeit dem Ergebnis soweit nähern müssen, dass ich hinreichend sicher sein kann…
Ich habe mir gedacht, dass die Lösungswahrscheinlichkeit x auf Grund der Unendlichkeit des Waldes gleich der Wahrscheinlichkeit ist, von einer beliebigen Verzweigung aus zum erstenmal wieder einen Schritt rückwärts zu gehen, und dass damit gilt
x = 1/3 (1 + 2/3 x + 4/9 x^2 + ...) = 1/3 ∑((2/3 x)^i; i=0..∞) = 1/(3 - 2x)
(geometrische Reihe), woraus
x^2 - 3/2 x + 1/2 = 0
mit der Lösung < 1 (...)
x = 1/2
folgt.
Ich habe es mit Hilfe vom Pascalschen Dreieck gelöst. Nach n-Schritten erhält man durch die Koeffizienten im Dreieck die Anzahl der Wege, die an diese Position führen.
Die Wahrscheinlichkeiten aller Wege, die am Waldrand oder außerhalb ankommen (eins höher als der Startort), muss man addieren. Von den Wegen, die innerhalb ankommen, muss man noch diejenigen addieren, die zwischendurch mindestens einmal am Waldrand waren.
Für die erste Summe gilt ∑ (n über k) (2/3)^(n-k) (1/3)^k für k = n/2 (aufgerundet) …n und für die zweite Summe ∑ (n über (k-1)) (2/3)^(n-k) (1/3)^k für k = 1 … n/2 (abgerundet)
Anschließend habe ich die Summen für große n vom Computer ausrechnen lassen.
Nicht so elegant, wie die Rechnungen oben, mit dem Pascalschen Dreieck aber eine schöne Veranschaulichung.
Ich hab‘s mir vorgestellt als Spiel: Wirf jeweils eine (unfaire) Münze mit Gewinnwahrscheinlichkeit = 2/3. Bei Gewinn gibt’s für Gimli 1 Geldeinheit, bei Verlust muss er 1 Geldeinheit abgeben. Gimli startet mit 1, der Wald mit +inf, aber sagen wir mal 100. Gesucht ist die Wahrscheinlichkeit von Gimlis Ruin. („x Geldeinheiten zu haben“ bedeutet „x Lichtungen vom Ausgang entfernt zu sein“, „zu gewinnen“ bedeutet eine Lichtung tiefer in den Wald zu gehen, „zu verlieren“ entsprechend das Gegenteil. Landet Gimli bei 0, dann ist er draußen.) Formeln gibt’s dann z.B. hier: https://de.m.wikipedia.org/wiki/Ruin_des_Spielers
Spannend finde ich, dass sich seine Entkommenswahrscheinlichkeit pro entfernterer Lichtung jeweils halbiert. Oder dass er mit Wahrscheinlichkeit = 1 von jeder beliebigen Lichtung herausfinden würde, wenn die Wahrscheinlichkeit bei der Wege-Auswahl zwischen „weiter rein“ und „wieder raus“ bei 50:50 liegen würde.
Ich habe es zum einen mit einer unendlichen Markowkette gelöst. Da die Übergangswahrscheinlichkeiten konstant sind, konnte man mit einer kleinen Umformung nachvollziehen, dass sich die Wahrscheinlichkeiten von Stufe zu Stufe halbieren müssen. Quasi ne diskrete DGL mit Anfangsbedingung.
In einer lösungsvariante habe ich mit einem cas Programm (Maple) die W-Keit direkt bestimmt.
Nachdem man (Hinweis in der Aufgabe) die Lichtungen in Äquivalenzklassen bezüglich ihres Abstandes zum Ausgang zusammengefasst hat,
gelangt man zu einer unsymmetrische Irrfahrt auf der Halbgeraden.
Ich vermute, dass es für einige Schüler mancher Bundesländer gut möglich war, auf die hier schon öfter angesprochene quadratische Gleichung zu kommen.
Das echte Problem bei der Aufgabe für mich scheint zu sein, wie man (als Schüler) rigoros deren zweite Lösung (p=1, Antwortmöglichkeit 10) ausschließen kann.
Man beachte, dass die symmetrische Irrfahrt in der Tat rekurrent wäre!
Ich habe mich bei der Beschäftigung mit der Aufgabe besonders gefreut, mal wieder mit Catalan-Zahlen und Dyck-Worten in Berührung zu kommen.
(12-13-2024, 09:04 AM)saltus schrieb: Nachdem man (Hinweis in der Aufgabe) die Lichtungen in Äquivalenzklassen bezüglich ihres Abstandes zum Ausgang zusammengefasst hat,
gelangt man zu einer unsymmetrische Irrfahrt auf der Halbgeraden.
Ich vermute, dass es für einige Schüler mancher Bundesländer gut möglich war, auf die hier schon öfter angesprochene quadratische Gleichung zu kommen. Das echte Problem bei der Aufgabe für mich scheint zu sein, wie man (als Schüler) rigoros deren zweite Lösung (p=1, Antwortmöglichkeit 10) ausschließen kann.
Man beachte, dass die symmetrische Irrfahrt in der Tat rekurrent wäre!
Ich habe mich bei der Beschäftigung mit der Aufgabe besonders gefreut, mal wieder mit Catalan-Zahlen und Dyck-Worten in Berührung zu kommen.
Ist es denn möglich, den Ausschluss dieser zweiten Lösung (p=1) kurz und gleichzeitig formal korrekt zu begründen? Da hatte ich nämlich auch Schwierigkeiten und musste mich auf meine Intuition verlassen, die da hieß: 2/3 (> 1/2) bewegt sich ja schließlich tendenziell eher tiefer in den Wald hinein als in Richtung Ausgang (1/3 < 1/2).
Mein Mann wollte es nicht glauben. Ich habe es über eine unendliche Reihe gelöst.