Markoffkette

08.09.2007, 19:12

bluemchen

Markoffkette

Hallo zusammen,

ich habe folgende Markoffkette. gehe mit wahrscheinlichkeit $\begin{eqnarray*} p_i \end{eqnarray*}$ von i zu i+1.
Und mit wahrscheinlichkeit $\begin{eqnarray*} 1- p_i \end{eqnarray*}$ von i nach 0.

Die Frage ist nun, ob diese Markoffkette rekurrent ist.

Ich denke nun es reicht zu zeigen, dass 0 rekurrent ist, da ja ganz $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ eine einzige Äquivalenzklasse ist.
Stimmt dies? und ist dies so, da je zwei elemente aus $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ gegenseitig erreichbar sind?

Also und ich möchte nun zeigen, dass 0 rekurrent ist.
Da kann ich ja zeigen, dass $\begin{eqnarray*} f_{00}=1 \end{eqnarray*}$ (also w'keit, dass ich wieder nach 0 zurückkehre)
Weiter gilt folgendes:
$\begin{eqnarray*} f_{00}= \sum_{n=0}^\infty~f_{00}^{(n)} \end{eqnarray*}$ ( $\begin{eqnarray*} f_{00}^{(n)} \end{eqnarray*}$ ist w'keit dass ich nach n schritten zum ersten mal wieder zur 0 gelange)

ich weiss, dass ich auf $\begin{eqnarray*} f_{00}= 1- \prod_{i=0}^\infty~p_i \end{eqnarray*}$ kommen sollte, weiss jedoch nicht wie.

Meiner Meinung nach ist, $\begin{eqnarray*} f_{00}^{(1)}=0 \end{eqnarray*}$ und $\begin{eqnarray*} f_{00}^{(2)}=1-p_1 \end{eqnarray*}$ . Ich weiss jedoch nicht ob das stimmt, und komme auch nicht weiter.

Hoffe dass mir jemand helfen kann.

Lieben Gruss.

09.09.2007, 10:11

bluemchen

Auf diesen Beitrag antworten »

also ich hab mir jetzt folgendes überlegt, vielleicht kann da ja schnell jemand drüberschaun, danke smile

Also, die wkeit, dass ich jemals wieder zur Null gelange:

$\begin{eqnarray*} f_{00}&=& p_0(1-p_1)+p_0 p_1(1-p_2) + p_0 p_1 p_2 (1-p_3) ...\\ &=& p_0 - p_0 p_1 +p_0 p_1 -p_0 p_1 p_2 + p_0 p_1 p_2 + ....\\&=& p_0 -\prod_{i=0}^\infty~p_i = 1- \prod_{i=0}^\infty~p_i \end{eqnarray*}$ (da ich ja von der null eins nur zur 1 gehen kann)

Ich nehme nun an, dass es von den $\begin{eqnarray*} p_i's \end{eqnarray*}$ abhängt ob das =1 oder nicht. $\begin{eqnarray*} 1- \prod_{i=0}^\infty~p_i =1 \end{eqnarray*}$ wenn die $\begin{eqnarray*} p_i's \end{eqnarray*}$ genügend klein sind.
Kann man das noch präzisieren?

Wäre froh wenn mir jemand sagen könnte ob das wirklich stimmt was ich gemacht hab Augenzwinkern

dankeschön

Edit (Dual Space): Zeilenumbruch eingefügt.

13.09.2007, 02:43

Tomtomtomtom

Auf diesen Beitrag antworten »

So einfach ist das nicht ganz, aber die Produkte haben shcon etwas damit zu tun.

Ein Zustand i heißt ja glaube ich rekurrent, wenn die Wahrscheinlichkeit, vom Startzustand i aus irgendwann wiederum i zu erreichen 1 ist. Ohne mir jetzt sicher zu sein, denke ich mal eine Markovkette heißt rekurrent, wenn alle Zustände rekurrent sind.

Erstmal stimmt es nicht, daß es reicht, die 0 zu betrachten, und von diesem Ergebnis auf alle Zustände zu schließen.

Betrachte zum Beispiel eine Markovkette, in der irgendein p_k=0 ist. Dann wirst du aus diesem Zustand garantiert wieder zur 0 geschickt. Also können alle Zustände, die nach k kommen, gar nicht rekurrent sein, weil es dann nur zwei verschiedene Arten von Realisierungen der Markovkette gibt:
Die einen kommen irgendwann zur 0, und laufen danach maximal wieder bis k, aber niemals weiter (da man ja von dort garantiert wieder bei 0 landet). Und die anderen (wobei das genaugenommen nur eine einzige Realisierung ist) laufen nach k einfach weiter durch alle natürlichen Zahlen.

Wenn man weiterhin den kleinsten solchen Index k mit p_k=0 wählt, sind alle Zustände mit i<k ganz bestimmt rekurrent. Die Wahrscheinlichkeit, da0 man von i aus irgendwann die 0 erreicht ist 1, daß passiert ja spätestens, wenn man bei k ankommt. Und von der 0 aus kann man die Wahrscheinlichkeiten abschätzen, wieder zu i zu kommen. Diese konvergiert mit wachsender Länge der Realisierung der Markovkette gegen 1 (siehe unten/Edit); die Wahrscheinlichkeit, den Zustand i irgendwann wieder zu erreichen ist also 1, also der Zustand rekurrent.

'Es gibt noch weitere "pathologische" Fälle, aber ich betrachte erstmal den "Normalfall" 0<p_i<1 für alle i. Betrachte ein beliebiges k aus IN. Dann ist die Wahrscheinlichkeit, von k aus in spätestens n Schritten wieder bei 0 zu landen gleich

$\begin{eqnarray*} (1-p_k)+p_k(1-p_{k+1})+p_kp_{k+1}(1-p_{k+2})+\ldots=1-\prod_{i=k}^{k+n} p_i \end{eqnarray*}$

Die Folge der Partialprodukte (also der Teil nach dem Minuszeichen für "n gegen unendlich") ist aufgrund der Voraussetzungen, die wir an die p_i gemacht haben, monoton fallend (da p_i<1) und beschränkt gegen 0, also auf jeden Fall konvergent. Fragt sich nur noch wogegen.

Gegen ein p>1 kann es nicht konvergieren, da schon p_k<1.

Es kann sein, daß das Produkt gegen ein p mit 0<p<1 konvergiert. In diesem Fall ist schon die Wahrscheinlichkeit, jemals die 0 zu erreichen, nicht gleich 1, das ist aber Voraussetzung dafür, jemals wieder zu k zu kommen . Damit ist also der Zustand nicht rekurrent, also auch nicht die gesamte Markovkette.

Bleibt der Fall, daß die Reihe der Partialprodukte gegen 0 konvergiert. Dann ist die Wahrscheinlichkeit, die 0 zu erreichen gleich 1. Und dann kann man wieder die Wahrscheinlichkeit abschätzen, k wieder zu erreichen, diese ist ebenfalls 1, siehe unten. In diesem Fall ist der Zustand k also rekurrent.

Wenn nun die gesamte Markovkette rekurrent sein soll, muß jeder Zustand rekurrent sein, also $\begin{eqnarray*} \prod_{i=k}^{\infty} p_i=0 \end{eqnarray*}$ für jedes k. Dafür ist hinreichend und notwendig, daß die gesamte Reihe $\begin{eqnarray*} \prod_{i=0}^{\infty} p_i=0 \end{eqnarray*}$ ist, was gerade heißt, daß der Zustand 0 rekurrent ist. Hier hast du also recht, nur die Begründung war nicht so ganz richtig.

Das Thema der Konvergenz von solchen unendlichen Produkten ist nicht so ganz Standardstoff, am ehesten wirst du dazu vielleicht in Lehrbüchern zur Funktionentheorie fündig, weil man einige Ergebnisse daraus für die Produktsätze holomorpher Funktionen benötigt.

Hinreichend aber trotzdem noch recht schwach (und für wohl fast jede nicht zu exotische Markovkette erfüllt) für $\begin{eqnarray*} \prod_{i=0}^{\infty} p_i=0 \end{eqnarray*}$ ist zum Beispiel die Bedingung, daß es ein r<1 gibt, so daß p_i<r für mindestens unendlich viele i (egal wie dünn sie wirklich gesäht sind, hauptsache unendlich viele).

Edit: Ok, hab die Lücken füllen können:
Betrachte ein k aus IN. Wir wollen zeigen, daß für die oben definierte Markovkette (mit 0<p_i<1 für alle i<k) mit Startzustand "0" mit wachsender Länge der Realisierung die Wahrscheinlichkeit des erneuten Eintretens von k gegen 1 geht.

Wenn wir uns im Zustand 0 befinden, ist die Wahrscheinlichkeit, daß wir wieder bei der 0 landen, ohne vorher k erreicht zu haben gleich

$\begin{eqnarray*} (1-p_0)+p_0(1-p_1)+\ldots+ p_0\ldots p_{k-2}(1-p_{k-1})=1-\prod_{i=0}^{k-1} p_i \end{eqnarray*}$

Wie man leicht sieht, ist in jeder beliebigen Realisierung der Markovkette der Zustand 0 der am häufigsten eintretende Zustand (möglicherweise nicht eindeutig, aber das ist egal). Betrachte jetzt eine Realisierung der Länge nk mit einem n aus IN. Wenn der Zustand k nicht wieder erreicht wird, muß es nach dem Schubfachprinzip einen Zustand geben, der mindestens n mal erreicht wird, dies gilt also auch für den Zustand 0 (da dieser am häufigsten auftritt). Die Wahrscheinlichkeit q, daß der Zustand k nicht eintritt, ist nun höchstens so groß wie Wahrscheinlichkeit, daß man bei n "Starts" von 0 nie direkt den Zustand k erreicht. Also gilt wegen dem oben schon aufgeschriebenen:

$\begin{eqnarray*} q\leq (1-\prod_{i=0}^{k-1} p_i)^n \end{eqnarray*}$

Der Ausdruck in der Klammer ist aufgrund der Voraussetzungen an die p_i echt kleiner als 1. Für n gegen unendlich geht also q gegen 0, also die Wahrscheinlichkeit des Eintretens von k gegen 1.

13.09.2007, 14:02

Auf diesen Beitrag antworten »

Eine schöne ausführliche Diskussion dieser Markov-Kette. Freude

Bleibt nur begrifflich festzuhalten, dass man in diesem Fall hier

Zitat:

Original von Tomtomtomtom
Es kann sein, daß das Produkt gegen ein p mit 0<p<1 konvergiert. In diesem Fall ist schon die Wahrscheinlichkeit, jemals die 0 zu erreichen, nicht gleich 1, das ist aber Voraussetzung dafür, jemals wieder zu k zu kommen . Damit ist also der Zustand nicht rekurrent, also auch nicht die gesamte Markovkette.

von der Transienz aller Zustände sprechen kann.

Generell kann man für den Fall " $\begin{eqnarray*} 0<p_i<1 \end{eqnarray*}$ für alle $\begin{eqnarray*} i \end{eqnarray*}$ " folgendes sagen: Alle Zustände sind dann miteinander verbunden, und zeigen somit dasselbe Rekurrenzverhalten. D.h., es sind entweder alle transient, alle alle positiv rekurrent oder alle nullrekurrent. Die Unterscheidung zwischen letzten beiden war hier nicht gefragt, ist aber auch ganz interessant.

Neue Frage »

Antworten »

Markoffkette

Verwandte Themen