Münzspiel

06.04.2024, 18:06

Marius1

Münzspiel

Meine Frage:
Anna würft startet mit der Zahl 1 und wirft nacheinander eine faire Münze, bei Kopf erhöht sie ihre Zahl um 1 und bei Zahl multipliziert sie ihre Zahl mit 2. Wie oft muss Anna ihre Münze werfen, bis ihre Zahl ein Vielfaches von 2024 ist?

Meine Ideen:
Sich hier einzelne Wahrscheinlichkeiten anzusehen ist vielzu komplex, hier muss es doch irgendeinen Trick geben ...

06.04.2024, 18:19

nichteuerernst

Auf diesen Beitrag antworten »

RE: Münzspiel
Die Frage ist nicht korrekt gestellt. Worum geht es?
-Mindestanzahl der Würfe?
-Erwartungswert für die erforderliche Anzahl?

06.04.2024, 19:26

Marius1

Auf diesen Beitrag antworten »

Tut mir leid, gemeint ist der Erwartungswert für die erforderliche Anzahl.

10.04.2024, 15:37

Marius1

Auf diesen Beitrag antworten »

Auf der Suche nach ähnlichen Aufgaben bin ich auf die Idee gestoßen, eine Markovkette auf Z/2024Z zu betrachten. Jedoch bin ich von alleine immer noch nicht auf die Lösung gekommen

11.04.2024, 13:28

willyengland

Auf diesen Beitrag antworten »

Interessante Aufgabe.
Bin nur Laie!

Da Kopf und Zahl gleich wahrscheinlich sind, könnte man überlegen, was rauskommt, wenn immer abwechselnd Kopf und Zahl kommen.
Dann ergibt sich die Zahlenfolge
1, 4, 10, 22, 46 ...

https://oeis.org/A033484

Danach würde man nach ca. 20 Würfen über 2024 kommen ...

11.04.2024, 15:24

HAL 9000

Auf diesen Beitrag antworten »

Die Mindestanzahl bekommt man raus, wenn man die Binärdarstellung von 2024 betrachtet: $\begin{eqnarray*} [11111101000]_2 \end{eqnarray*}$

Jede 1 steht für Kopf, und jede Stellenverrückung für Zahl, wir starten aber bereits mit einer 1. Damit benötigt man im Idealfall $\begin{eqnarray*} 6+10=16 \end{eqnarray*}$ Würfe, um auf genau 2024 zu kommen (Sequenz ZKZKZKZKZKZZKZZZ).

Man könnte sich noch fragen, ob ein Vielfaches von 2024 nicht doch schneller erreicht werden kann: Das hat zwar mehr Binärstellen, aber ggfs. weniger Einsen darin, was die Schrittzahl vermindert. Nach kurzem Durchprobieren stellt man aber fest, dass es ein solches Vielfaches nicht gibt. Augenzwinkern

Eine Maximalzahl gibt es nicht: Wirft man beispielsweise immer Zahl, so bekommt man nur Zweierpotenzen $\begin{eqnarray*} 2^n \end{eqnarray*}$ , welche nie durch 2024 teilbar sind.

Für die mittlere Schrittzahl, d.h. Erwartungswert, fällt mir leider auch nichts besseres ein als das:

Zitat:

Original von Marius1
Auf der Suche nach ähnlichen Aufgaben bin ich auf die Idee gestoßen, eine Markovkette auf Z/2024Z zu betrachten.

Das ist zumindest eine naheliegende Idee, auch wenn es in eine monstermäßig große Ü-Matrix der Dimension 2024 mündet:

0 ist absorbierender Zustand, d.h. $\begin{eqnarray*} p_{0,0}=1 \end{eqnarray*}$ .
Dann ist $\begin{eqnarray*} p_{1,2}=1 \end{eqnarray*}$ .
Für $\begin{eqnarray*} r\notin\{0,1\} \end{eqnarray*}$ ist $\begin{eqnarray*} p_{r,r+1} = p_{r,2r} = \frac{1}{2} \end{eqnarray*}$ , alle Indizes versteht sich modulo 2024 betrachtet.
Für alle nicht genannten Paare gilt $\begin{eqnarray*} p_{r,s}=0 \end{eqnarray*}$ .

Ähnlich kann man auch ein Gleichungssystem für die mittlere Schrittzahl $\begin{eqnarray*} s_r \end{eqnarray*}$ bis zur Erreichung des Zustandes 0 berechnen, ausgehend von Zustand $\begin{eqnarray*} r\bmod 2024 \end{eqnarray*}$ :

Klar ist $\begin{eqnarray*} s_0=0 \end{eqnarray*}$ , denn man ist ja schon am Ziel, außerdem $\begin{eqnarray*} s_1 = s_2+1 \end{eqnarray*}$ sowie $\begin{eqnarray*} s_r = \frac{s_{r+1}+s_{2r}}{2}+1 \end{eqnarray*}$ für alle $\begin{eqnarray*} 2\leq r\leq 2023 \end{eqnarray*}$ .

Man löst also dieses 2024x2024-LGLS und am Ende ist $\begin{eqnarray*} s_1 \end{eqnarray*}$ das, was man sucht. Augenzwinkern

Die Lösung ist (ohne Gewähr) $\begin{eqnarray*} s_1\approx 2222.655 \end{eqnarray*}$ .

11.04.2024, 22:43

Marius1

Auf diesen Beitrag antworten »

Danke für deine Antwort, ich bin mittlerweile auch zu einer Lösung gekommen, jedoch leider einer anderen...

Ich habe mich gestern nochmal ein bisschen zu Markovketten schlau gemacht. Die Markovkette ist irreduzibel und aperiodisch, d.h. sie besitzt eine eindeutige stationäre Verteilung, welche wenn ich mich nicht irre eine Gleichverteilung sein sollte (jeder Eintrag des Vektors ist $\begin{eqnarray*} \frac{1}{2024} \end{eqnarray*}$ ). Weiterhin gibt es für Markovketten ( $\begin{eqnarray*} X_0, X_1, ... \end{eqnarray*}$ ) die Erstwiederkehrzeit $\begin{eqnarray*} \tau_x = \left\{ t\geq 1 |X_t = x\right\} \end{eqnarray*}$ für eine Kette, die im Zustand $\begin{eqnarray*} x \end{eqnarray*}$ startet und die POSITIVE Zeit bis zur Wiederkehr in den Zustand $\begin{eqnarray*} x \end{eqnarray*}$ misst. Diese steht in Verbindung mit der stationären Verteilung, es gilt $\begin{eqnarray*} \mathbb E(\tau_x)=\frac{1}{\pi(x)} \end{eqnarray*}$ , wobei $\begin{eqnarray*} \pi \end{eqnarray*}$ der Vektor der stationären Verteilung sein soll.

Für unsere Markovkette bedeutet das ja, dass wenn wir in Zustand $\begin{eqnarray*} 0 \end{eqnarray*}$ starten, wir nach $\begin{eqnarray*} 2024 \end{eqnarray*}$ Schritten erwarten können wieder in diesem Zustand zu landen. Unter Verwendung deiner Notation haben wir $\begin{eqnarray*} s_0 = \frac{s_0+s_1}{2}+1 \end{eqnarray*}$ und mit $\begin{eqnarray*} s_0=2024 \end{eqnarray*}$ erhalte ich den Wert $\begin{eqnarray*} s_1=2022 \end{eqnarray*}$

12.04.2024, 08:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Marius1
Ich habe mich gestern nochmal ein bisschen zu Markovketten schlau gemacht. Die Markovkette ist irreduzibel und aperiodisch, d.h. sie besitzt eine eindeutige stationäre Verteilung

Das ist richtig, sofern man ein wenig anders modelliert als ich oben: D.h., wenn man Zustand $\begin{eqnarray*} r=0 \end{eqnarray*}$ nicht als absorbierend, sondern als ganz "normalen" Zustand sieht wie die anderen $\begin{eqnarray*} r\neq 1 \end{eqnarray*}$ , d.h. mit $\begin{eqnarray*} p_{0,0} = p_{0,1} = \frac{1}{2} \end{eqnarray*}$ . Kann man auch machen, ja.

Zitat:

Original von Marius1
welche wenn ich mich nicht irre eine Gleichverteilung sein sollte (jeder Eintrag des Vektors ist $\begin{eqnarray*} \frac{1}{2024} \end{eqnarray*}$ ).

Es ist ein grundsätzlicher Irrtum zu glauben, alle Stationaritätsverteilungen müssten die Gleichverteilung sein. Im vorliegenden Fall kann man das sogar ganz einfach widerlegen:

Beispielsweise kommt man in den Zustand 2 auf zwei mögliche Weisen - einmal vom Zustand 1 aus immer (egal ob durch +1 oder *2), oder aber vom Zustand 1013 aus durch *2. Es muss daher im Stationaritätsfall gelten

$\begin{eqnarray*} p_2 = p_1 + \frac{1}{2}p_{1013} \end{eqnarray*}$ .

Das ist aber durch die Gleichverteilung $\begin{eqnarray*} p_k = \frac{1}{2024} \end{eqnarray*}$ schlicht nicht erfüllt.

P.S.: Hast du mal eine Simulation gemacht, um die Plausibilität deines Resultats 2022 zu überprüfen? Würde ich dir auf jeden Fall empfehlen. smile

EDIT: Hab inzwischen mal noch ein bisschen mehr rumgerechnet: Die tatsächlichen Stationaritätswahrscheinlichkeiten sind

$\begin{eqnarray*} p_{8k+r} = \frac{a_r}{64515} \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq 252 \end{eqnarray*}$ sowie $\begin{eqnarray*} 0\leq r\leq 7 \end{eqnarray*}$ und $\begin{eqnarray*} (a_r)_{r=0,\ldots,7} = (58,29,40,20,44,22,28,14) \end{eqnarray*}$ ,

d.h. sie hängen nur von der Zustandsnummer modulo 8 ab. Und es gilt exakt $\begin{eqnarray*} s_1=\frac{64457}{29} \end{eqnarray*}$ .

EDIT2: Interessant ist, wenn wir 2024 durch einen beliebigen Modul $\begin{eqnarray*} m \end{eqnarray*}$ ersetzen, den Rest so lassen, dann passiert folgendes:

Sei $\begin{eqnarray*} m = u\cdot 2^v \end{eqnarray*}$ mit einer ungeraden Zahl $\begin{eqnarray*} u \end{eqnarray*}$ , dann ist Stationaritätswahrscheinlichkeit $\begin{eqnarray*} p_k \end{eqnarray*}$ nur von $\begin{eqnarray*} k\bmod 2^v \end{eqnarray*}$ abhängig. Im Sonderfall $\begin{eqnarray*} v=0 \end{eqnarray*}$ (d.h. $\begin{eqnarray*} m \end{eqnarray*}$ ungerade) haben wir damit dann tatsächlich die von Marius1 vermutete Gleichverteilung als stationäre Verteilung. In diesem Fall - aber nur diesem! - scheint dann $\begin{eqnarray*} s_1=2m-2 \end{eqnarray*}$ zu gelten. Ob es bei $\begin{eqnarray*} v\geq 1 \end{eqnarray*}$ auch eine Regelmäßigkeit gibt, wäre wohl noch zu eruieren.

EDIT 3 (22.4.): Schade, Marius scheint das Interesse verloren zu haben. Oder er will sich erst Grundkenntnisse in Markov-Ketten aneignen, bevor er wieder einsteigt.

Neue Frage »

Antworten »

Münzspiel

Verwandte Themen