Unendliches Würfeln bis alle Augenzahlen einmal vorgekommen sind

Question

Sie werfen ein faires Tetraeder so lange, bis jede der 4 Augenzahlen mindestens einmal erschienen ist. Die Zufallsvariable \( Y \) zähle die Anzahl der Würfe, die Sie dafür benötigen. Wir modellieren Sie die Situation durch eine Folge von unabhängigen auf \( \{1,2,3,4\} \) gleichverteilten Zufallsvariablen \( X_{1}, X_{2}, \ldots \)

(i) Definieren Sie \( Y \) mithilfe der Zufallsvariablen \( X_{1}, \ldots \)
(ii) Beschreiben Sie die Verteilung von \( Y \), d.h. \( \mathbb{P}_{Y} \), mittels Angabe der Zähldichte.
(iii) Sei für \( i=1,2,3,4 \) die Zufallsvariable \( Y_{i} \) die Wartezeit, zwischen \( i-1 \) und \( i \) verschiedenen Augenzahlen. Definieren Sie \( Y_{i} \).
(iv) Bestimmen Sie die Verteilung von \( Y_{i} \).

Problem/Ansatz: Bei (i) definiere ich Y = min( n aus N : {\( X_{1}, X_{2}, \ldots \)} = {1,2,3,4})
Nun weiss ich bei (ii) nicht weiter, ich möchte ja P(Y = n) berechnen, aber ich weiß nicht wie ich da jetzt weiter vorgehe, denn der Ereignisraum müsste hier ja aus unendlichen Folgen bestehen, wie soll ich denn dann die Wahrscheinlichkeit berechnen, es müsste ja sein P(Y = 4) + P(Y = 5) + ..... = 1 aber was sollen, dann die einzelnen P(Y = n) sein. Das einzige was mir einfällt ist irgendwas mit der geometrischen Verteilung zu machen, denn die ist so ähnlich definiert wie ich hier Y defniert habe, aber eine wirkliche Verbindung sehe ich da auch nicht.

Comments

Weißt du, was eine Markovkette ist? Du kannst das Problem als Markovkette beschreiben, sodass deine gesuchte Verteilung mittels etwas linearer Algebra gefunden werden kann.

---

Ne, wir haben ZV erst grade eingeführt

---

Da ihr ZV gerade erst eingeführt habt, habt ihr sicherlich die geometrische Verteilung behandelt. Schau mal nach dem Coupon Collector Problem.

---

@joners Wie sähe der Ansatz über Markovketten aus? Kannst du da näher drauf eingehen?

---

Unter https://de.wikipedia.org/wiki/Sammelbilderproblem steht etwas dazu.

Answer 1

Ich nehme mal an der Würfel habe \( N \) Seiten, damit die Notation einfacher wird. Dann gilt
\(\begin{aligned} \mathbf{P}( Y = n) &= \sum_{ k = 1}^{ n} \mathbf{P}( Y = n |X_{ n}  = N) \mathbf{P}( X _{ n}  = k) \\ &= \frac{n}{ N} \mathbf{P}( \{ X_{ 1} , \ldots , X_{ n - 1} \} = \{ 1, \ldots , N - 1\}) . \end{aligned}\)

Nun setzen wir
\( A_{ k}  = \{ k \in \{ X_{ 1} , \ldots , X_{ n - 1} \}\} \) und finden
\(\begin{aligned} \mathbf{P}( \{ X_{ 1} , \ldots , X_{ n - 1} \} = \{ 1, \ldots , N - 1\}) &= \mathbf{P}\biggl( \bigcap_{ k = 1}^{ N - 1} A_{ k}\cap A_{ N}^{ c}  \biggr) = 1 - \mathbf{P}\biggl( \bigcup_{ k = 1}^{ N - 1} A_{ k}^{ c} \cup A_{ N}\biggr) \end{aligned}\)
was wir jetzt z.B. mittels Inklusion/Exklusion berechnen können:
\(\begin{aligned} \mathbf{P}\biggl( \bigcup_{ k = 1}^{ N - 1} A_{ k}^{ c} \cup A_{ N}\biggr) &= \sum_{ \substack{ \varnothing \neq J \subset \{ 1, \ldots , N - 1\}} } ( -1) ^{ |J| + 1} \mathbf{P}\biggl(  \bigcap_{ j \in J}^{ } A_{ j} ^{ c} \biggr) +  \sum_{ \substack{ \varnothing \neq J \subset \{ 1, \ldots , N\} \\ N \in J} } ( -1) ^{ |J| + 1} \mathbf{P}\biggl( \bigcap_{ j \in J}^{ } A_{ j} ^{ c} \cap A_{ N} \biggr) . \end{aligned}\)
Nun berechnen wir
\(\begin{aligned} \mathbf{P}\biggl( \bigcap_{ j \in J}^{ } A_{ j}^{ c} \biggr) = \Bigl( 1 - \frac{ |J|}{ N} \Bigr) ^{ n - 1} \end{aligned}\)
und
\(\begin{aligned} \mathbf{P}\biggl( \bigcap_{ j \in J}^{ } A_{ j} ^{ c}\cap A_{ N} \biggr) = \frac{1}{ N} \sum_{ k = 1}^{ n - 1} \mathbf{P}\biggl( \bigcap_{ j \in J}^{ } A_{ j} ^{ c}| X_{ k}  = N\biggr) = \frac{ n - 1}{ N} \Bigl( 1 - \frac{ |J|}{ N} \Bigr) ^{ n - 2}. \end{aligned}\)
Da die Terme nur von \( |J| \) abhängen (also nur von der Kardinalität der Menge), vereinfacht sich die Inklusions/Exklusions Formel nach einsetzten
der obigen Rechnungen zu
\(\begin{aligned} \mathbf{P}\biggl( \bigcup_{ k = 1}^{ N - 1} A_{ k}^{ c} \cup A_{ N}\biggr)= \sum_{ j = 1}^{ N - 1}(-1)^{ j + 1} \binom{ N - 1}{ j}\Bigl(  \Bigl( 1 - \frac{ j}{ N} \Bigr) ^{ n - 1} + \frac{ n - 1}{ N} \Bigl( 1 - \frac{ j}{ N} \Bigr) ^{ n - 2}\Bigr). \end{aligned}\)
Wenn du jetzt alles zusammenfürst wird der Ausdruck für \( N = 4 \) natürlich deutlich weniger bedrohlich wirken.

Comments

danke für die antwort, habe einen etwas anderen naivieren lösungsweg genutzt, aber der sieht interessant aus. werd ich mir mal gründlicher anschauen wenn ich mehr zeit hab