Markov-Ketten

08.06.2007, 15:55

daveking256

Markov-Ketten

Hallo,

ich hätte da ein Problem mit Markov-Ketten.
Gegeben sei eine Markov-Kette mit zwei Zuständen G(=GOOD) und B(=BAD). Die Übergangswahrscheinlichekeiten P(G->B) (d.h. von GOOD nach BAD) und P(B->G) seinen auch bekannt. Daraus können dann P(B->B) und P(G->G) problemlos ermittelt werden).

Meine Frage lautet: wie groß ist die Wahrscheinlichkeit bei n Versuchen genau k-mal im Zustand B(=BAD) zu landen?

Hinweis:
Die Wahrscheinlichkeit im Zustand BAD P(B) oder Zustand GOOD P(G) zu beginnen lässt sich folgendermaßen berechnen:

P(B)=P(G->B)/(P(G->B)+P(B->G))
und
P(G)=P(B->G)/(P(G->B)+P(B->G))

Die Anzahl aller Kombinationen die die obige Bedingung k aus n erfüllen lässt sich wie wie folgt berechnen:
n!/(k! (n-k)!)

Man könnte nun all diese n!(k! (n-k)!) Kombinationen aufschreiben und die jeweiligen Wahrschinlichkeiten berechnen, was aber für große n ein Problem darstellt. Deshalb suche ich nach einem geschlossenen Ausdruck.

Ich wäre froh, wenn mir jemand mit meinem Problem weiterhelfen könnte.

Grüße

Dave

08.06.2007, 16:11

Auf diesen Beitrag antworten »

Zitat:

Original von daveking256
Meine Frage lautet: wie groß ist die Wahrscheinlichkeit bei n Versuchen genau k-mal im Zustand B(=BAD) zu landen?

Du meinst natürlich an $\begin{eqnarray*} n \end{eqnarray*}$ aufeinanderfolgenden Zeitpunkten der Markovkette? $\begin{eqnarray*} n \end{eqnarray*}$ Versuche kann man auch fehldeuten...

Zitat:

Original von daveking256
Hinweis:
Die Wahrscheinlichkeit im Zustand BAD P(B) oder Zustand GOOD P(G) zu beginnen lässt sich folgendermaßen berechnen:

P(B)=P(G->B)/(P(G->B)+P(B->G))
und
P(G)=P(B->G)/(P(G->B)+P(B->G))

Das ist kein Hinweis, sondern (übersetzt) eine wichtige zusätzliche Information:

Dass nämlich die vorliegende Markovkette stationär ist, d.h. dass die Aufenthaltswahrscheinlichkeiten in jedem Zeitpunkt gleich sind.

Das ist wichtig, denn ansonst hängt die zu berechnende Wkt davon ab, zu welchem Zeitpunkt innerhalb der Markov-Kette man die n Werte abgreift. Nur im Falle der Stationarität ist das egal.

EDIT: Zur Vermeidung unnötiger Mehrarbeit anderer Helfer verweise ich mal noch auf die ähnlichen Threads des Fragestellers:

http://matheplanet.com/matheplanet/nuke/...&post_id=601840
http://www.matheraum.de/read?i=271166

09.06.2007, 12:29

daveking256

Auf diesen Beitrag antworten »

Um die Angabe nochmal zu verdeuttlchen:
-Es handelt sich natürlich um eine stationäre Markov-Kette.
-Wir betrachten n aufeinanderfolgende Zeitpunkte und wollen wissen wie groß die W'keit dabei ist genau k-mal im Zustand B zu landen.
-Der Anfangszustand der Kette ist beliebig, d.h. entweder B oder G
-Sollte es keinen geschlossenen Ausdruck für die gesuchte W'keit geben, würde mir eine Approximation weiterhelfen

09.06.2007, 12:38

Auf diesen Beitrag antworten »

Zitat:

Original von daveking256
-Es handelt sich natürlich um eine stationäre Markov-Kette.

So "natürlich" ist es nicht, wenn es nicht angegeben wird. Aber jetzt wissen wir es.

Zitat:

Original von daveking256
-Der Anfangszustand der Kette ist beliebig, d.h. entweder B oder G

Was heißt beliebig? Er muss der von dir angegebenen Anfangsverteilung

$\begin{eqnarray*} p_0(B) = \frac{P(G\to B)}{P(G\to B)+P(B\to G)},\quad p_0(G) = \frac{P(B\to G)}{P(G\to B)+P(B\to G)} \end{eqnarray*}$

genügen, sonst ist die Stationarität nicht erfüllt!

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

Ansonsten einige Vorüberlegungen: Sei $\begin{eqnarray*} b:=P(G\to B) \end{eqnarray*}$ sowie $\begin{eqnarray*} g:=P(B\to G) \end{eqnarray*}$ . Dann ist

$\begin{eqnarray*} P = \begin{pmatrix} 1-b & b\\ g & 1-g\end{pmatrix} \end{eqnarray*}$

die Übergangsmatrix der Markovkette $\begin{eqnarray*} (X_n)_{n=1,2,\ldots} \end{eqnarray*}$ mit den zwei Zuständen $\begin{eqnarray*} \{G,B\} \end{eqnarray*}$ (in der Reihenfolge in der Matrix). Ich nehme mal an, es geht um den allgemeinen Fall $\begin{eqnarray*} 0<b<1,0<g<1 \end{eqnarray*}$ , denn sollte einer der Werte die Extrema 0 oder 1 annehmen, wird's wirklich trivial.

Ok, die stationäre Verteilung $\begin{eqnarray*} p_s = \begin{pmatrix} \frac{g}{g+b}\\[2ex] \frac{b}{g+b}\end{pmatrix} \end{eqnarray*}$ , also die mit $\begin{eqnarray*} p_s = P^T\cdot p_s \end{eqnarray*}$ , haben wir oben schon diskutiert. Du interessierst dich nun für die Verteilung der Zufallsgröße

$\begin{eqnarray*} N_n \end{eqnarray*}$ ... Anzahl BAD in $\begin{eqnarray*} X_1,\ldots,X_n \end{eqnarray*}$

Der Fall $\begin{eqnarray*} b+g=1 \end{eqnarray*}$ ist trivial: Da liegt Unabhängigkeit der $\begin{eqnarray*} X_n \end{eqnarray*}$ vor, und man bekommt einfach die Binomialverteilung $\begin{eqnarray*} N_n\sim B(n,b) \end{eqnarray*}$ .

In allen anderen Fällen liegt diese Unabhängigkeit nicht vor und es wird schwierig: Die Formel für den Erwartungswert $\begin{eqnarray*} E(N_n) \end{eqnarray*}$ ist einfach machbar, für die Varianz sehe ich auch noch gewisse Chancen, aber für die genaue Verteilung? verwirrt

Für die lassen sich leicht Rekursionsformeln angeben, aber inwieweit man die in explizite Ausdrücke überführen kann, überblicke ich noch nicht.

09.06.2007, 14:26

daveking256

Auf diesen Beitrag antworten »

Sollte es nicht möglich sein eine explizite Formel zu finden, wären der Erwartungswert und die Varianz ein Hilfe für mich, um ein Gefühl für die Verteilung zu bekommen. Desweiteren könnten mir evtl. auch die Rekursionsformeln weiterhelfen. Wäre für einen Hinweis dankbar.

09.06.2007, 14:58

Auf diesen Beitrag antworten »

Man kann sich der Sache am besten nähern, wenn man "etwas mehr" berechnet:

$\begin{eqnarray*} p_G(n,k) \end{eqnarray*}$ ... Wahrscheinlicheit für genau k-mal BAD und zum Schluss GOOD
$\begin{eqnarray*} p_B(n,k) \end{eqnarray*}$ ... Wahrscheinlicheit für genau k-mal BAD und zum Schluss BAD

Dann suchst du gerade die Summe dieser beiden Werte. Die Aufschlüsselung hat den Vorteil, das ganze für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ rekursiv schreiben zu können:

$\begin{eqnarray*} p_G(n,k) = (1-b) \cdot p_G(n-1,k) + g \cdot p_B(n-1,k) \quad\text{für}\quad 0\leq k<n \end{eqnarray*}$
$\begin{eqnarray*} p_B(n,k) = b \cdot p_G(n-1,k-1) + (1-g) \cdot p_B(n-1,k-1)\quad\text{für}\quad 1\leq k\leq n \end{eqnarray*}$

Start ist natürlich $\begin{eqnarray*} n=1 \end{eqnarray*}$ mit den Werten der stationären Startverteilung:

$\begin{eqnarray*} p_G(1,0)=\frac{g}{g+b},\quad p_G(1,1)=0,\quad p_B(1,0)=0,\quad p_B(1,1)=\frac{b}{g+b} \end{eqnarray*}$ .

EDIT: Ach ja, der Erwartungswert - der ist aufgrund der Stationarität einfach

$\begin{eqnarray*} E(N_n) = \frac{nb}{g+b} \end{eqnarray*}$ .

Mit der Varianz ist es doch etwas aufwändiger, als ich gedacht hatte...

Neue Frage »

Antworten »

Markov-Ketten

Verwandte Themen