Wahrscheinlichkeit Froschhüpfen

11.08.2024, 09:57

Froschkoenig

Wahrscheinlichkeit Froschhüpfen

Meine Frage:
Gegeben ist ein Kreis von 2022 numerierten Seerosen (1,...,2022,1,...). Ein Frosch sitzt auf Seerose 1 und geht in jedem Schritt mit gleicher Wahrscheinlichkeit nach links oder rechts. Berechne die Wahrscheinlichkeit, dass der Frosch, wenn er zum ersten Mal die Rose 1012 erreicht, bereits alle anderen Seerosen besucht hat.

Meine Ideen:
Der Frosch muss ja einmal den Weg von 1 bis 1011 zurücklegen und dann wieder rückwärts über die 1 Hinweg sich der 1012 von hinten nähern (bzw. die gleiche Variante spiegelverkehrt). Allerings weiß ich nicht so recht weiter, da der Frosch auf seinem Weg willkürlich vor und zurück gehen kann und es so schwiewrig ist alle Pfade zu erfassen, welche zum Ziel führen. Gibt es hier vielleicht Trick?

13.08.2024, 11:18

HAL 9000

Auf diesen Beitrag antworten »

Verallgemeinerung: $\begin{eqnarray*} 2n \end{eqnarray*}$ Seerosen und der Weg von 1 bis zum Ersterreichen von $\begin{eqnarray*} n+1 \end{eqnarray*}$ . Gesucht ist Wahrscheinlichkeit $\begin{eqnarray*} p_n \end{eqnarray*}$ , dass man dann alle anderen Seerosen bereits besucht hat.

Lösung: Sei $\begin{eqnarray*} q_{n,k} \end{eqnarray*}$ die Wahrscheinlichkeit, bei der symmetrischen einfachen Irrfahrt nach $\begin{eqnarray*} k \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

Dann gilt $\begin{eqnarray*} q_{n,0} = 1 \end{eqnarray*}$ für $\begin{eqnarray*} n>0 \end{eqnarray*}$ sowie $\begin{eqnarray*} q_{0,k} = 0 \end{eqnarray*}$ für $\begin{eqnarray*} k>0 \end{eqnarray*}$ . Über die Rekursion $\begin{eqnarray*} q_{n,k} = \frac{q_{n-1,k+1} + q_{n+1,k-1}}{2} \end{eqnarray*}$ für $\begin{eqnarray*} n>0,k>0 \end{eqnarray*}$ kommt man zur expliziten Darstellung $\begin{eqnarray*} q_{n,k} = \frac{n}{n+k} \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 0,k\geq 0 \end{eqnarray*}$ mit $\begin{eqnarray*} n+k>0 \end{eqnarray*}$ .

Zum vorliegenden Problem besteht der Zusammenhang $\begin{eqnarray*} p_n = 2\left( q_{n,n-1} - q_{n,n} \right) = \frac{1}{2n-1} \end{eqnarray*}$ .

Genauere Erklärung:

$\begin{eqnarray*} q_{n,n-1} \end{eqnarray*}$ ist ja die Wahrscheinlichkeit, bis zu $\begin{eqnarray*} n-1 \end{eqnarray*}$ zu kommen, bevor man $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.
$\begin{eqnarray*} q_{n,n} \end{eqnarray*}$ ist entsprechend die Wahrscheinlichkeit, sogar bis zu $\begin{eqnarray*} n \end{eqnarray*}$ zu kommen, bevor man $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

Demzufolge ist $\begin{eqnarray*} q_{n,n-1}-q_{n,n} \end{eqnarray*}$ die Wahrscheinlichkeit, nach rechts bis zu $\begin{eqnarray*} n-1 \end{eqnarray*}$ und nicht weiter zu kommen, bevor man links $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

Aus Symmetriegründen bekommmt man dieselbe Wahrscheinlichkeit, nach links bis zu $\begin{eqnarray*} -(n-1) \end{eqnarray*}$ und nicht weiter zu kommen, bevor man rechts $\begin{eqnarray*} n \end{eqnarray*}$ erreicht.

Beides zusammen ergibt die gesuchte Wahrscheinlichkeit $\begin{eqnarray*} p_n \end{eqnarray*}$ .

EDIT (19.8.): Der Froschkönig scheint verstummt zu sein. unglücklich

19.08.2024, 18:01

DrummerS

Auf diesen Beitrag antworten »

Interessantes Thema. Im Fall von z.B. n = 3 wäre dann $\begin{eqnarray*} p_{n} = \frac{1}{2 \cdot 3 - 1}= \frac{1}{5} \end{eqnarray*}$

$\begin{eqnarray*} \begin{matrix} && Seerosen \left(n=3\right) && & & Pfade \\ &&4&& & & 1 \to 2 \to 3 \to 4 \\ &3&&5& & & 1 \to 2 \to 3 \to 2 \\ & && & & & 1 \to 2 \to 1 \to 6 \\ &2&&6& & & 1 \to 6 \to 1 \to 2 \\ &&1&& & &1 \to 6 \to 5 \to 6 \end{matrix} \end{eqnarray*}$

Die Pfade $\begin{eqnarray*} 1 \to 2 \to 1 \to 2 \end{eqnarray*}$ und $\begin{eqnarray*} 1 \to 6 \to 1 \to 6 \end{eqnarray*}$ scheiden aus, da bezüglich Seerose 1 die Bedingung "...mit gleicher Wahrscheinlichkeit nach links oder rechts.." verletzt wäre.

19.08.2024, 18:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von DrummerS
Die Pfade $\begin{eqnarray*} 1 \to 2 \to 1 \to 2 \end{eqnarray*}$ und $\begin{eqnarray*} 1 \to 6 \to 1 \to 6 \end{eqnarray*}$ scheiden aus, da bezüglich Seerose 1 die Bedingung "...mit gleicher Wahrscheinlichkeit nach links oder rechts.." verletzt wäre.

Wieso sollen die ausscheiden? Erstaunt1

Gleiche Wahrscheinlichkeit nach links wie rechts heißt doch nicht, dass beim zweiten Passieren von 1 es zwingend in die andere Richtung gehen muss. unglücklich

Das ist ein sehr schräges Verständnis von Wahrscheinlichkeit - dann glaubst du wohl auch, dass die Lotto-Zahlen dieser Woche sämtlich nächste Wochhe nicht dran sein dürfen, damit die Statistik wieder stimmt. Augenzwinkern

19.08.2024, 18:35

DrummerS

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
...Das ist ein sehr schräges Verständnis von Wahrscheinlichkeit - dann glaubst du wohl auch, dass die Lotto-Zahlen dieser Woche sämtlich nächste Wochhe nicht dran sein dürfen, damit die Statistik wieder stimmt. Augenzwinkern

Sehr guter Vergleich Freude

. Vielen Dank! Das zeigt mir, dass ich es (noch) nicht verstanden habe!

19.08.2024, 19:08

HAL 9000

Auf diesen Beitrag antworten »

Selbstverständlich kann man alle Pfade betrachten, die von 1 bis erstmals zur 4 führen: Hat ein solcher Pfad die Länge $\begin{eqnarray*} m \end{eqnarray*}$ (die hier ungerade sein muss) hat er die Wahrscheinlichkeit $\begin{eqnarray*} p = \frac{1}{2^m} \end{eqnarray*}$ . Das sind aber eben unendlich viele Pfade.

Die Summe all dieser Wahrscheinlichkeiten ist gleich 1 (ist nicht ganz trivial in der Begründung).

Jetzt greift man sich nur die Pfade heraus, wo sämtliche Knoten von 1-6 vorkommen, das sind ebenfalls unendlich viele. Die Summe von deren Wahrscheinlichkeiten ist nun zu bestimmen.

Und da muss man sich eben eine Art rekursives Vorgehen überlegen, um diese unendlich vielen Pfade zu bändigen bzw. zu beherrschen - z.B. so wie oben von mir überlegt.

19.08.2024, 19:56

Froschkoenig

Auf diesen Beitrag antworten »

Der Froschkönig musste sich erst vom ganzen Hüpfen erholen und bedankt sich nun für die Lösung.
Da wäre ich nicht von allein drauf gekommen...

21.08.2024, 10:17

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Wahrscheinlichkeit Froschhüpfen

Zitat:

Original von Froschkoenig
Meine Frage:
Gegeben ist ein Kreis von 2022 numerierten Seerosen (1,...,2022,1,...). Ein Frosch sitzt auf Seerose 1 und geht in jedem Schritt mit gleicher Wahrscheinlichkeit nach links oder rechts.

Ich habe das alles mit Interesse gelesen. Was mich hier aber zunächst sehr wundert ist, was links und rechts mit aufsteigender oder absteigender Nummerierung zu tun haben soll. Das wurde hier nämlich nicht festgelegt. Es wurde weder festgelegt, ob der Seerosenkreis mit oder gegen den Uhrzeigersinn nummeriert ist. Auch wurde nicht festgelegt, ob man von außen auf den Kreis schaut oder von innen. Gibt es zum Rätsel eine einschlägig bekannte Zeichnung? verwirrt

21.08.2024, 10:23

HAL 9000

Auf diesen Beitrag antworten »

Für die gestellte Frage ist es offenkundig völlig belanglos, ob im oder entgegen dem Uhrzeigersinn 1,2,...,2021,2022 nummeriert wurde.

Zitat:

Original von Ulrich Ruhnau
Gibt es zum Rätsel eine einschlägig bekannte Zeichnung? verwirrt

Für $\begin{eqnarray*} n=6 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} 2n=12 \end{eqnarray*}$ wäre z,B. eine gewöhnliche (Analog-)Uhr eine passende Skizze. Augenzwinkern

21.08.2024, 14:27

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Rekursion $\begin{eqnarray*} q_{n,k} = \frac{q_{n-1,k+1} + q_{n+1,k-1}}{2} \end{eqnarray*}$ für $\begin{eqnarray*} n>0,k>0 \end{eqnarray*}$

$\begin{eqnarray*} p_n = 2\left( q_{n,n-1} - q_{n,n} \right) = \frac{1}{2n-1} \end{eqnarray*}$ .

Demzufolge ist $\begin{eqnarray*} q_{n,n-1}-q_{n,n} \end{eqnarray*}$ die Wahrscheinlichkeit, nach rechts bis zu $\begin{eqnarray*} n-1 \end{eqnarray*}$ und nicht weiter zu kommen, bevor man links $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

Mein Problem ist, daß ich Mühe habe, zu verstehen, wie die Rekursion funktioniert. Deshalb waren Hinweise wie rechts und links unverständlich.

21.08.2024, 14:37

HAL 9000

Auf diesen Beitrag antworten »

Ok, dazu wiederhole ich zunächst mal, was dieser Wert bedeutet:

Zitat:

Original von HAL 9000
Sei $\begin{eqnarray*} q_{n,k} \end{eqnarray*}$ die Wahrscheinlichkeit, bei der symmetrischen einfachen Irrfahrt nach $\begin{eqnarray*} k \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

"Symmetrische einfach Irrfahrt" bedeutet, dass man bei 0 startet und bei jeder Position mit Wahrscheinlichkeit $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ nach links (d.h. negative Richtung) bzw. nach rechts (d.h. positive Richtung) genau einen Schritt tätigt.

D.h., im ersten Schritt geht man mit Wahrscheinlichkeit $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ nach links und erreicht Position -1. Die Wahrscheinlichkeit nun, von -1 startend nach $\begin{eqnarray*} k \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht entspricht (durch Indexverschiebung) exakt der Wahrscheinlichkeit, von 0 startend nach $\begin{eqnarray*} k+1 \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n+1 \end{eqnarray*}$ erreicht, d.h., dem Wert $\begin{eqnarray*} q_{n-1,k+1} \end{eqnarray*}$ .

Genauso geht man mit Wahrscheinlichkeit $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ nach rechts und erreicht Position 1. Die Wahrscheinlichkeit nun, von 1 startend nach $\begin{eqnarray*} k \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht entspricht (wieder durch Indexverschiebung, aber in die andere Richtung) exakt der Wahrscheinlichkeit, von 0 startend nach $\begin{eqnarray*} k-1 \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n-1 \end{eqnarray*}$ erreicht, d.h., dem Wert $\begin{eqnarray*} q_{n+1,k+1} \end{eqnarray*}$ .

Beide Pfade aufgesammelt bekommt man $\begin{eqnarray*} q_{n,k} = \frac{q_{n-1,k+1}+q_{n+1,k-1}}{2} \end{eqnarray*}$ , selbstredend so nur gültig im Fall $\begin{eqnarray*} n>0,k>0 \end{eqnarray*}$ .

----------------------------------------------------------

Dazu sollte man natürlich noch folgendes wissen. In meiner Lösung oben habe ich den kreisförmigen Teich erstmal umnumeriert:

1) Aus $\begin{eqnarray*} 1,\ldots,2022 \end{eqnarray*}$ habe ich $\begin{eqnarray*} 0,\ldots,2021 \end{eqnarray*}$ gemacht, allgemein $\begin{eqnarray*} 0,\ldots,2n-1 \end{eqnarray*}$ , damit wurde aus Zielfeld 1012 die 1011, allgemein $\begin{eqnarray*} n \end{eqnarray*}$ .

2) Nun habe ich den Kreis an der Zielposition $\begin{eqnarray*} n \end{eqnarray*}$ "aufgebrochen" in eine Gerade, d.h. die Positionen $\begin{eqnarray*} 1,\ldots,n-1 \end{eqnarray*}$ bleiben erhalten und auch $\begin{eqnarray*} n \end{eqnarray*}$ als eine (!) mögliche Zielposition.

Die Positionen $\begin{eqnarray*} 2n-1,2n-2,\ldots,n+1 \end{eqnarray*}$ werden hingegen modulo $\begin{eqnarray*} 2n \end{eqnarray*}$ betrachtet zu $\begin{eqnarray*} -1,-2,\ldots,-n+1 \end{eqnarray*}$ , und wir haben als weitere Zielposition $\begin{eqnarray*} -n \end{eqnarray*}$ .

3) Das Ereignis, von dem hier die Wahrscheinlichkeit bestimmt werden soll, kann man im Kontext dieser Umdeutung auf der $\begin{eqnarray*} \mathbb{Z} \end{eqnarray*}$ -Achse der einfachen diskreten Irrfahrt dann so beschreiben:

Von 0 startend ist man beim ersten Erreichen von $\begin{eqnarray*} -n \end{eqnarray*}$ in der anderen Richtung genau bis hin zu $\begin{eqnarray*} n-1 \end{eqnarray*}$ gekommen oder beim ersten Erreichen von $\begin{eqnarray*} n \end{eqnarray*}$ in der anderen Richtung genau bis hin zu $\begin{eqnarray*} -n+1 \end{eqnarray*}$ gekommen.

Genau das drückt dann $\begin{eqnarray*} p_n = 2\left( q_{n,n-1} - q_{n,n} \right) \end{eqnarray*}$ aus.

22.08.2024, 04:20

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Lösung: Sei $\begin{eqnarray*} q_{n,k} \end{eqnarray*}$ die Wahrscheinlichkeit, bei der symmetrischen einfachen Irrfahrt nach $\begin{eqnarray*} k \end{eqnarray*}$ zu gelangen, bevor man erstmals $\begin{eqnarray*} -n \end{eqnarray*}$ erreicht.

die Rekursion $\begin{eqnarray*} q_{n,k} = \frac{q_{n-1,k+1} + q_{n+1,k-1}}{2} \end{eqnarray*}$

Bedeuten n und k nach dem ersten Hüpfer immer noch das Gleiche wie vor dem ersten Hüpfer? Gehen wir doch mal vom Zifferblatt einer Uhr aus. Der Frosch sitzt auf der 6 und will auf die 12. Ich nehme an, daß die Rekursionsformel sagen will, daß die Wahrscheinlichkeit von 6 auf 12 zu kommen ohne vorher auf der 11 gelandet zu sein gleich dem Durchschnitt der Wahrscheinlichkeiten ist, bei der 5 oder der 7 zu beginnen und dann zur 12 zu gelangen, ohne jeweils zuvor auf die 11 gekommen zu sein. Aber dann wird der n- oder k-Parameter die Anzahl der nicht oder doch gewünschten Hüpfer in die eine oder andere Richtung wiedergeben. Was davon sehe ich jetzt richtig?

22.08.2024, 05:09

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
Ich nehme an, daß die Rekursionsformel sagen will, daß die Wahrscheinlichkeit von 6 auf 12 zu kommen ohne vorher auf der 11 gelandet zu sein gleich dem Durchschnitt der Wahrscheinlichkeiten ist, bei der 5 oder der 7 zu beginnen und dann zur 12 zu gelangen, ohne jeweils zuvor auf die 11 gekommen zu sein.

Nein, du hast das "Aufbrechen" des Kreises und die Überführung auf die Gerade und dann die symmetrische Irrfahrt leider nicht richtig verstanden.

Versuche, das mit der Irrfahrt auf der Gerade zu verstehen und führe erst dann den gedanklichen Übergang wieder zum Kreis her, welcher in der Formel $\begin{eqnarray*} p_n = 2\left( q_{n,n-1} - q_{n,n} \right) \end{eqnarray*}$ mündet.

Ich hab auch erst versucht, die Rekursion allein auf dem Kreis zu bilden und zu verstehen, was aber am Ende nicht funktioniert hat - deswegen ja dieser Zugang über den Umweg "Gerade".

22.08.2024, 05:48

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
2) Nun habe ich den Kreis an der Zielposition $\begin{eqnarray*} n \end{eqnarray*}$ "aufgebrochen" in eine Gerade, d.h. die Positionen $\begin{eqnarray*} 1,\ldots,n-1 \end{eqnarray*}$ bleiben erhalten und auch $\begin{eqnarray*} n \end{eqnarray*}$ als eine (!) mögliche Zielposition.

Die Positionen $\begin{eqnarray*} 2n-1,2n-2,\ldots,n+1 \end{eqnarray*}$ werden hingegen modulo $\begin{eqnarray*} 2n \end{eqnarray*}$ betrachtet zu $\begin{eqnarray*} -1,-2,\ldots,-n+1 \end{eqnarray*}$ , und wir haben als weitere Zielposition $\begin{eqnarray*} -n \end{eqnarray*}$ .

HAL, das Problem besteht darin, richtig zu verstehen, was du mit k und n jeweils meinst. Deshalb habe ich dein Beispiel mit der Uhr gebracht. Könntest du vielleicht anhand der Ziffern exemplarisch ausdrücken was du meinst ohne gleich mit k und n zu verallgemeinern?

22.08.2024, 06:31

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ sind natürliche Zahlen - und was sie in dem Kontext bedeuten, habe ich ausführlich erläutert.

Aber gut, die Uhr:

$\begin{eqnarray*} q_{6,5} \end{eqnarray*}$ beschreibt beispielsweise die Wahrscheinlichkeit, dass man von der 6 startend erst die 1 erreicht bevor man über die 11 zur 12 gelangt. Es beinhaltet aber auch die Pfade, dass man dabei von der 1 weiter bis zur 12 (oder gar noch weiter darüber hinaus) gelangt, was wir hier nicht wollen.

P.S.: Gewöhn dir bitte mal an, den ausführlichen und wohlüberlegten Erklärungen zu folgen und zu versuchen die zu verstehen, statt diese zu ignorieren und stattdessen auf dich zugeschnittene Erklärungen in deinem festgelegten Kontext einzufordern. unglücklich

22.08.2024, 21:09

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
P.S.: Gewöhn dir bitte mal an, den ausführlichen und wohlüberlegten Erklärungen zu folgen und zu versuchen die zu verstehen, statt diese zu ignorieren und stattdessen auf dich zugeschnittene Erklärungen in deinem festgelegten Kontext einzufordern. unglücklich

Als wenn ich das nicht immer versuchen würde! traurig

Ich hatte nur das Problem, daß es hier offensichtlich darum geht, daß mit n und k die Entfernungen zu den Zielfeldern angegeben werden. n und k sind also Abstände bezogen auf den Ausgangspunkt und nicht die Nummern der Zielfelder. Danke für das nachgeschobene konkrete Beispiel HAL!

Ich habe mir erlaubt, mit Matlab den Fall einer Uhr n=6 also 12 Seerosenblätter zu simulieren und zur Kontrolle eine Statistik darüber zu entwickeln wie häufig im Schnitt jedes Seerosenblatt Besuch bekommt, wenn der Frosch von Seerosenblatt Nr. 6 zu Seerosenblatt Nr. 12 bzw. 0 hüpft. Die Blaue Statistik zeigt alle 1,1 Millionen Versuche gemittelt. [attach]57880[/attach][attach]57881[/attach]Die rote Statistik greift sich die 0,1 Millionen Versuche heraus, wo der Frosch erst dann Feld 12 erreicht, wenn alle anderen Felder abgegrast sind. Die grüne Statistik gibt den Rest wieder und zeigt, wie oft der Frosch Feld 12 erreicht, ohne alle anderen Felder besucht zu haben, nämlich 1 Million mal.[attach]57882[/attach]

Auch hier zeigt sich eindrucksvoll, daß HAL mal wieder recht hat mit seiner Formel und so soll es ja auch sein. Augenzwinkern

$\begin{eqnarray*} p_n = 2\left( q_{n,n-1} - q_{n,n} \right) = \frac{1}{2n-1}=\frac 1{11} \end{eqnarray*}$

23.08.2024, 05:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
Ich hatte nur das Problem, daß es hier offensichtlich darum geht, daß mit n und k die Entfernungen zu den Zielfeldern angegeben werden. n und k sind also Abstände bezogen auf den Ausgangspunkt und nicht die Nummern der Zielfelder.

Allerdings, und so steht es von Anfang an in meinen Erläuterungen:

Zitat:

Ich wiederhole gern nochmal: Da steht $\begin{eqnarray*} {\color{red}-n} \end{eqnarray*}$ statt $\begin{eqnarray*} n \end{eqnarray*}$ . Mit diesem Satz sollte für Normallesende eigentlich klar sein, dass es um eine Position $\begin{eqnarray*} k \end{eqnarray*}$ Schritte nach der einen, und eine weitere Position $\begin{eqnarray*} n \end{eqnarray*}$ Schritte nach der anderen Seite geht!!! Dass so früh das Verständnis aussetzt, kann ich ja nicht ahnen. unglücklich

===========================================================

Etwas weiter gedacht: Bei insgesamt $\begin{eqnarray*} m \end{eqnarray*}$ Blättern numeriert mit $\begin{eqnarray*} 0,1,\ldots,m-1 \end{eqnarray*}$ im Kreis führen wir die Hüpferei startend bei 0 solange fort, bis alle Blätter mindestens einmal aufgesucht worden. Das letzte Blatt, was aufgesucht wurde, trage die Nummer $\begin{eqnarray*} s \end{eqnarray*}$ , und dies geschehe mit Wahrscheinlichkeit $\begin{eqnarray*} p_{m,s} \end{eqnarray*}$ .

Oben haben wir nachgewiesen $\begin{eqnarray*} p_{2n,n} = \frac{1}{2n-1} \end{eqnarray*}$ . Tatsächlich kann man mit derselben Methode das fast noch mehr verblüffende $\begin{eqnarray*} p_{m,s}=\frac{1}{m-1} \end{eqnarray*}$ gültig für alle $\begin{eqnarray*} m\geq 2 \end{eqnarray*}$ sowie $\begin{eqnarray*} s=1,\ldots,m-1 \end{eqnarray*}$ nachweisen!!!

Mit anderen Worten: Bei beliebig gewählter Vorgabe von Start- und Zielblatt (müssen nur unterschiedlich sein) ist die Wahrscheinlichkeit, erstmals das Zielblatt zu betreten und dabei alle anderen Blätter schon mindestens einmal aufgesucht zu haben stets gleich $\begin{eqnarray*} \frac{1}{m-1} \end{eqnarray*}$ , ganz egal wie weit die beiden voneinander entfernt sind. Kannst gern nochmal deine Simulation anwerfen und das nachvollziehen. Augenzwinkern

23.08.2024, 15:42

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Ja, ich habe meine Simulation noch mal gestartet für 11 Millionen Versuche und die Startposition diesmal auf Feld 1 statt Feld 6. Die Wahrscheinlichkeit hat sich dadurch jedoch nicht verändert. Sie ist für 12 Seerosenblätter schon wieder $\begin{eqnarray*} \frac 1{11} \end{eqnarray*}$ .
[attach]57883[/attach][attach]57884[/attach][attach]57885[/attach]

23.08.2024, 21:37

HAL 9000

Auf diesen Beitrag antworten »

Ich meine die veränderte Simulation, immer solange zu hüpfen, bis alle Blätter besucht wurden - und dann notieren, welches dabei jeweils das letzte besuchte Blatt war. Bei $\begin{eqnarray*} 11\cdot 10^8 \end{eqnarray*}$ Simulationen (Dauer 51s bei 8 Threads) auf einem zwölfblättrigem Teich kam in meiner Simulation dann folgendes Ergebnis

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:	1: 100018395 2: 100007934 3: 99998192 4: 100002477 5: 100003869 6: 99983518 7: 100007201 8: 99988654 9: 99999990 10: 99999262 11: 99990508

24.08.2024, 21:32

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Die Frage wäre dann nur noch, wie oft der Frosch im Schnitt hüpfen muß, bis er zufällig alle Blätter erreicht hat. Was mich aber viel mehr interessiert: HAL, in welcher Programmiersprache hast du deine Simulation geschrieben? Ist es für dich so leicht, 8 Threads parallel ablaufen zu lassen, daß du nicht mal 10 min länger wartest um mit einem Thread auszukommen verwirrt

25.08.2024, 12:09

HAL 9000

Auf diesen Beitrag antworten »

C++, und das ganze auf einem 8 Jahre altem PC (i4790K).

War auch deshalb so schnell, weil die gute Qualität des von mir verwendeten Zufallszahlengenerators MT 19937 es gestattete, sämtliche Bits der Zufallszahlen zu verwenden. D.h. jede generierte 64Bit-Zufallszahl konnte für 64 Hüpfer verwendet werden. Augenzwinkern

Zitat:

Original von Ulrich Ruhnau
Ist es für dich so leicht, 8 Threads parallel ablaufen zu lassen, daß du nicht mal 10 min länger wartest um mit einem Thread auszukommen verwirrt

Ich hab mir vor längerer Zeit (als das anfing mit den Mehrkernprozessoren im PC) ein Template-Projekt für Stochastik-Simulationen geschrieben, welches im wesentlichen den ganzen Verwaltungsaufwand für die Threadaufteilung sowie Initialisierung der Zufallszahlengeneratoren übernimmt. Bei neuen Projekten (wie z.B. dem hier) muss ich dann im wesentlichen nur die Prozedur für die Einzelsimulation neu schreiben, sowie die dazu nötige Datenstrukturen für In- und Output anpassen.

Sehr wichtig ist, dass jeder Thread seinen eigenen Pseudozufallszahlen-Generator bekommt (also eigentlich ist es derselbe MT19937, aber mit verschiedenen Startwerten), denn ansonsten stockt/stottert der Simulationsfluss an diesem "Flaschenhals".

Zitat:

Original von Ulrich Ruhnau
Die Frage wäre dann nur noch, wie oft der Frosch im Schnitt hüpfen muß, bis er zufällig alle Blätter erreicht hat.

Beim 12-blättrigem Seerosenteich wurden in obiger Simulation insgesamt $\begin{eqnarray*} 72\,600\,486\,248 \end{eqnarray*}$ Hüpfer ausgeführt, das ergibt im Mittel 66 Hüpfer pro Durchlauf. Meine (bisher unbewiesene) Vermutung lautet allgemein $\begin{eqnarray*} \frac{m(m-1)}{2} \end{eqnarray*}$ . Hier hängt allerdings die mittlere Schrittzahl von der erreichten Endposition $\begin{eqnarray*} k \end{eqnarray*}$ der Hüpferei ab: Und zwar ist da die mittlere Schrittzahl gleich $\begin{eqnarray*} \frac{m(7m-8)}{12} - \left(k-\frac{m}{2}\right)^2 \end{eqnarray*}$ .

Alles durch Simulation erhalten und bedarf noch des Beweises.

Neue Frage »

Antworten »

Wahrscheinlichkeit Froschhüpfen

Verwandte Themen