Markov-Kette, Würfeln

15.06.2017, 20:29

Sabbse92

Markov-Kette, Würfeln

Hallo zusammen,

Man wirft wiederholt einen (fairen) Würfel. Sei $\begin{eqnarray*} X_n \end{eqnarray*}$ das Mininum der Ausgänge bis zum n-ten Wurf.

Ich verstehe noch nicht genau, was $\begin{eqnarray*} X_n \end{eqnarray*}$ genau angibt, könnte mir das bitte mal jemand an einem Bsp. erklären.

Ich soll zeigen, dass $\begin{eqnarray*} X_n \end{eqnarray*}$ eine zeithomogene Markovkette mit Zustandsraum $\begin{eqnarray*} \{1,2,3,4,5,6,\} \end{eqnarray*}$ ist.

Genügt es, wenn ich die Übergangsmatrix $\begin{eqnarray*} p_{i,j} \end{eqnarray*}$ bestimme und folgende Gleichheit zeige:

$\begin{eqnarray*} \mathbb P(X_n = i_n | X_{n-1}= i_{n-1}, ...., X_0 = {i_0} ) = p_{i_{n-1} \medspace i_n} \end{eqnarray*}$

15.06.2017, 21:07

HAL 9000

Auf diesen Beitrag antworten »

RE: Markov-Kette, Würfeln

Zitat:

Original von Sabbse92
Man wirft wiederholt einen (fairen) Würfel. Sei $\begin{eqnarray*} X_n \end{eqnarray*}$ das Mininum der Ausgänge bis zum n-ten Wurf.

Ich verstehe noch nicht genau, was $\begin{eqnarray*} X_n \end{eqnarray*}$ genau angibt, könnte mir das bitte mal jemand an einem Bsp. erklären.

Nehmen wir an, wir haben als die ersten 10 Würfe

6, 4, 6, 5, 3, 5, 3, 1, 4, 2 .

Dann ist $\begin{align*} X_n \end{align*}$ für $\begin{align*} n=1,\ldots,10 \end{align*}$

6, 4, 4, 4, 3, 3, 3, 1, 1, 1

und beim Wert 1 bleibt das ganze auch im weiteren stehen, denn kleiner kann das Minimum ja nicht werden.

15.06.2017, 21:27

Sabbse92

Auf diesen Beitrag antworten »

Danke für die Erklärung!

Ich weiß leider immer noch nicht so genau wie ich zeigen soll, dass es sich um eine Zeithomogene Markovkette handelt..

Der zukünftige Zustand des Prozess ist nur durch den aktuellen Zustand bedingt. Wie soll ich das aber jetzt mathematisch zeigen?

15.06.2017, 21:39

HAL 9000

Auf diesen Beitrag antworten »

Bezeichnen wir mit $\begin{align*} Y_n \end{align*}$ die Augenzahl den $\begin{align*} n \end{align*}$ -ten Wurfes. Dann ist

$\begin{align*} X_n = \min(Y_1,\ldots,Y_n) \stackrel{!}{=} \min(\min(Y_1,\ldots,Y_{n-1}),Y_n) = \min(X_{n-1},Y_n) \end{align*}$ .

Da außerdem $\begin{align*} Y_n \end{align*}$ von $\begin{align*} \left\{X_1,\ldots,X_{n-2}\right\} \end{align*}$ unabhängig ist, ist klar, dass die bedingte Verteilung von $\begin{align*} X_n \end{align*}$ unter Bedingung $\begin{align*} X_{n-1} \end{align*}$ von der ferneren Vergangenheit $\begin{align*} \left\{X_1,\ldots,X_{n-2}\right\} \end{align*}$ nicht abhängt. Du kannst natürlich gern die genaue Ü-Matrix aufstellen, für die Beantwortung der bloßen Frage "liegt hier die Markov-Eigenschaft vor?" ist das aber nicht wirklich nötig.

15.06.2017, 22:07

Sabbse92

Auf diesen Beitrag antworten »

Okay, also ist es nicht immer zwingend notwendig dass mathematisch exakt zu zeigen, sondern man kann das ganze logisch begründen sowie du es gemacht hast.

Die Übergangsmatrix für diesen stochastischen Prozess, sieht doch wie folgt aus oder?

$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 &0 \\ 1/6 & 5/6 & 0 & 0 & 0 & 0 \\ 1/6 & 1/6 & 2/3 & & 0 & 0 \\ .... .... \\ 1/6 ..... & & & & & 1/6 \end{pmatrix} \end{eqnarray*}$

16.06.2017, 07:17

HAL 9000

Auf diesen Beitrag antworten »

Ja, die Ü-Matrix ist richtig. Freude

17.06.2017, 17:28

Heisenberg93

Auf diesen Beitrag antworten »

Ein Beweis ist nicht zwingend notwendig, lässt sich aber in den meisten Fällen einfachen zeigen.

17.06.2017, 17:31

Heisenberg93

Auf diesen Beitrag antworten »

Ein Beweis ist nicht zwingend notwendig, lässt sich aber in den meisten Fällen einfach zeigen.

Entschuldigung für den Doppel-Post.

17.06.2017, 18:05

Sabbse92

Auf diesen Beitrag antworten »

Könntest du bitte überprüfen ob die folgenden Aufgabe korrekt gelöst habe.

- Bestimmen Sie $\begin{eqnarray*} P_{1j}(n):=\mathbb P(X_n=j|X_0=1) \end{eqnarray*}$ $\begin{eqnarray*} \forall j\in S = \{1,2,..,6\} \end{eqnarray*}$

$\begin{eqnarray*} P_{1j}(n)= 1 , j=1 \end{eqnarray*}$ , ansonsten $\begin{eqnarray*} P_{1j}(n)= 0 , j \in S \setminus \{1\} \end{eqnarray*}$

-Ist die Kette irreduzibel?

Nein, weil $\begin{eqnarray*} \exists k=1 \in S , \forall n \in \mathbb N , \forall j \in S \setminus \{1\}: P_{kj}(n)=0 \end{eqnarray*}$

-Welche Zustände sind absorbierend?

Der Zustand $\begin{eqnarray*} \{k=1\} \end{eqnarray*}$ ist absorbierend, weil

$\begin{eqnarray*} \mathbb P (X_{n+1} \in S \setminus \{k\} | X_n = k ) = 0 \end{eqnarray*}$ ist

- Bestimmen Sie die Wahrscheinlichkeit $\begin{eqnarray*} p_{2,n} \end{eqnarray*}$ , dass , $\begin{eqnarray*} X_n>2 \end{eqnarray*}$ zu dem Zeitpunkt n.

Man beginnt bei Zustand 2 und soll die Wahrscheinlichkeit bestimmen in einen höheren Zustand zu gelangen? Falls ich die Aufgabe korrekt interpretiert habe, ist die W'keit 0.

18.06.2017, 10:03

HAL 9000

Auf diesen Beitrag antworten »

Sieht alles soweit richtig aus.

Beim letzten Punkt kann man allerdings

Zitat:

Original von Sabbse92
- Bestimmen Sie die Wahrscheinlichkeit $\begin{eqnarray*} p_{2,n} \end{eqnarray*}$ , dass , $\begin{eqnarray*} X_n>2 \end{eqnarray*}$ zu dem Zeitpunkt n.

die Formulierung auch anders interpretieren: $\begin{align*} p_{2,n} \end{align*}$ ist vielleicht wirklich direkt als Wahrscheinlichkeit $\begin{align*} P(X_n>2) \end{align*}$ gemeint! In dem Fall wäre dann doch noch etwas zu rechnen.

18.06.2017, 11:56

Sabbse92

Auf diesen Beitrag antworten »

Also wird die W'keit gesucht, dass man zum Zeitpunkt n $\begin{eqnarray*} X_n>2 \end{eqnarray*}$ erhält.

Hmm, es gibt doch einen Anfangszustands(-vektor) $\begin{eqnarray*} \vec{x}(0)= (x_1=1/6,x_2=1/6,...,x_6=1/6) \end{eqnarray*}$ , wobei $\begin{eqnarray*} x_i, i\in S \end{eqnarray*}$ die W'keit ist im Zustand i zu beginnen.

Wenn man jetzt $\begin{eqnarray*} P_{ij}(n) \end{eqnarray*}$ berechnet, kann man $\begin{eqnarray*} \vec{x}(n)=P_{ij}(n) \cdot \vec{x}(0) \end{eqnarray*}$ bestimmen. Dann ergibt sich die W'keit für $\begin{eqnarray*} X_n>2 \end{eqnarray*}$ aus der Summe $\begin{eqnarray*} \sum_{i=3}^6 \vec{x}(n)_i \end{eqnarray*}$

Das sieht aber ziemlich umständlich aus, um $\begin{eqnarray*} P_{ij}(n) \end{eqnarray*}$ zu bestimmen müsste diese erstmal Diagonalisieren. Gibt es einen einfacheren Weg?

18.06.2017, 15:12

HAL 9000

Auf diesen Beitrag antworten »

Man kann auch einfach zur ursprünglichen Definition von $\begin{align*} X_n \end{align*}$ gehen, unter Umgehung des Markov-Krams:

Zitat:

Original von Sabbse92
Man wirft wiederholt einen (fairen) Würfel. Sei $\begin{eqnarray*} X_n \end{eqnarray*}$ das Mininum der Ausgänge bis zum n-ten Wurf.

$\begin{align*} X_n>2 \end{align*}$ ist gleichbedeutend damit, dass alle Würfe $\begin{align*} 1\ldots n \end{align*}$ mit Augenzahlen aus $\begin{align*} \{3,4,5,6\} \end{align*}$ enden, damit ist $\begin{align*} P(X_n>2) = \left(\frac{2}{3}\right)^n \end{align*}$ .

18.06.2017, 16:22

Sabbse92

Auf diesen Beitrag antworten »

Das ist natürlich praktisch!

Vielen Dank für deine Hilfe Hal 9000.

Neue Frage »

Antworten »

Markov-Kette, Würfeln

Verwandte Themen