8. Markovketten 8.1. Homogene Markovketten In Diskreter Zeit

Transcript

8. MARKOVKETTEN 127 u u H 6 HH 6 u - u 6 HH H HH HH j u u   @    @  @   @  R @   u u - u  u Abbildung 8.1: Reduzible und periodische Markovkette 8. Markovketten 8.1. Homogene Markovketten in diskreter Zeit Ein Prozess {Xn : n ∈ IIN} heisst homogene Markovkette (in diskreter Zeit) mit (abz¨ahlbarem) Zustandsraum E, falls Xn ∈ E f¨ ur alle n ∈ IIN und IIP[Xn+1 = in+1 | X0 = i0 , . . . , Xn = in ] = IIP[X1 = in+1 | X0 = in ] f¨ ur alle n ∈ IIN und alle ik ∈ E, 0 ≤ k ≤ n + 1. Es gen¨ ugt den Fall E = IIN (I = ∞) oder E = {0, 1, . . . , I} f¨ ur ein I ∈ IIN zu betrachten. Wir setzen νi = IIP[X0 = i] und pij = IIP[X1 = j | X0 = i]. Sei ν = (ν0 , . . . , νI ) und P = (pij )i,j∈E falls I < ∞, mit der analogen Definition falls I = ∞. Wir haben dann f¨ ur die Verteilung von Xn IIP[Xn = i] = IIE[IIP[Xn = i | Xn−1 ]] = I X pji IIP[Xn−1 = j] = [(IIP[Xn−1 = j])j∈E P ]i . j=0 Mittels Induktion ist dies (IIP[Xn = i])i = (νP n )i . Definition 8.1. Wir sagen Zustand j ist erreichbar von i, falls es ein n gibt, so dass IIP[Xn = j | X0 = i] > 0. Wir sagen, die Markovkette ist irreduzibel, falls j erreichbar von i ist f¨ ur alle i, j ∈ E. Wir sagen eine Markovkette ist aperiodisch, falls f¨ ur alle i 1 der gr¨osste gemeinsame Teiler von {n ≥ 1 : IIP[Xn = i | X0 = i] > 0} ist. Ist der gr¨osste gemeinsame Teiler d > 1, so nennen wir die Markovkette periodisch mit Periode d. In Abbildung 8.1 ist in der Graphik links eine Kette abgebildet, in der der unterste Zustand nicht von den anderen erreicht werden kann. Die anderen Zust¨ande sind 128 8. MARKOVKETTEN  u ?  - u - u - u - u  - u ?  Abbildung 8.2: Markovkette von allen anderen aus erreichbar. L¨oscht man den untersten Zustand, so wird die Kette aperiodisch und irreduzibel. Die rechte Graphik ist eine irreduzible Kette mit Periode 3. Schreiben wir nun i ↔ j, falls i von j und j von i erreichbar ist. Falls es f¨ ur ein i kein j gibt, so dass i ↔ j, so wird die Markovkette den Zustand i verlassen und nie mehr zur¨ uckkehren oder f¨ ur immer in i bleiben. F¨ ur solche Zust¨ande interessieren ¨ wir uns nicht. Falls es keine solchen Zust¨ande gibt, ist ↔ eine Aquivalenzrelation. ¨ Wir k¨onnen also die Zust¨ande in Aquivalenzklassen unterteilen. Ein Markovpro¨ ¨ zess verl¨asst dann die Aquivalenzklasse nie, und wir k¨onnen jede Aquivalenzklassse gesondert betrachten. Daher werden wir nur irreduzible Markovketten betrachten. In einer irreduziblen Markovkette haben alle Zust¨ande die gleichen Perioden. Hat eine Markovkette Periode d, so gibt es d Mengen, so dass die Markovkette deterministisch durch diese d Mengen l¨auft. In diesem Fall wollen wir nur die Markovkette Xnd studieren, die dann aperiodisch ist. Daher werden wir nur aperiodische Markovketten betrachten. Sei nun I endlich. Ist die Markovkette irreduzibel und aperiodisch, dann gibt es ein n0 (da der gr¨osste gemeinsame Teiler 1 ist), so dass IIP[Xn0 = j | X0 = i] > 0 f¨ ur alle i, j. Betrachten wir die Eigenwerte von P , und nennen wir sie λ0 , . . . , λI . P Wir ordnen die Eigenwerte so, dass |λi | ≥ |λi+1 |. Da Ij=0 pij = 1, ist P e = e f¨ ur n0 > e = (1, . . . , 1) , also existiert ein Eigenwert 1. Die Matrix P hat die Eigenwerte λni 0 . Da P n0 e = e, und e echt positive Koordinaten hat, ist nach dem Perron– Fr¨obenius-Theorem λ0 = 1 und |λi | < λ0 = 1 f¨ ur i ≥ 1. e ist der einzige (Rechts-) Eigenvektor, der nur positive Koordinaten hat. Weiter gibt es einen (Links-) Eigenvektor π mit πi > 0 f¨ ur alle i. Wir haben dann, πP = π. Nach dem Perron– Fr¨obenius-Theorem ist dies der einzige Eigenvektor, der nur positive Eintr¨age hat. P Wir k¨onnen annehmen, dass Ii=0 πi = 1. Also ist {π} eine station¨are Verteilung. Da π der einzige Eigenvektor mit positiven Eintr¨agen ist, ist π eindeutig. Beispiel 8.2. Sei pi,i+1 = p ∈ (0, 1) f¨ ur 0 ≤ i < I, pi,i−1 = 1 − p f¨ ur 1 ≤ i ≤ I, pI,I = p und p0,0 = 1 − p. Dann sind alle anderen Eintr¨age 0. Die Kette ist in Abbildung 8.2 illustriert. Die Markovkette ist dann irreduzibel und aperiodisch. 8. MARKOVKETTEN 129 Wir m¨ ussen das Gleichungssystem πi = pπi−1 + (1 − p)πi+1 , 1 ≤ i ≤ I − 1 , π0 = (1 − p)(π0 + π1 ) , πI = p(πI−1 + πI ) l¨osen. Wir erhalten π1 = pπ0 /(1 − p), πi+1 = (πi − pπi−1 )/(1 − p), also πi = (p/(1 − p))i π0 . Dann ist die letzte Gleichung auch erf¨ ullt. Ist p 6= 21 , so ist die Randbedingung I  X p i 1 − p − p(p/(1 − p))I π0 = π0 . 1= 1−p 1 − 2p i=0 Also l¨asst sich π0 berechnen. Ist p = 21 , dann ist πi = π0 , und damit πi = (I + 1)−1 . Ist I = ∞, so folgern wir analog πi = (p/(1 − p))i π0 . Ist p < 12 , erhalten wir durch Summieren, π0 = (1 − 2p)/(1 − p), und damit πi = (1 − 2p)pi . (1 − p)i+1 Ist p ≥ 12 , dann sind die πi nur summierbar, falls π0 = 0. In diesem Falle existiert keine station¨are Verteilung. Wir werden die Kette mit I = ∞ und p ≥ 21 sp¨ater analysieren.  Proposition 8.3. Sei {Xn } eine irreduzible aperiodische Markovkette auf einem endlichen Zustandsraum. Dann existiert der Grenzwert πi = limn→∞ IIP[Xn = i | X0 = j] und ist unabh¨angig von j. Weiter gilt {π} ist eine station¨are Verteilung, und πi > 0 f¨ ur alle i. Beweis. (n) Sei Mj (n) = supi∈E (P n )ij und mj (n+1) mj = inf i∈E X = inf i∈E (P n )ij . Wir haben dann pik (P n )kj ≥ inf k∈E i∈E X (n) pik mj (n) = mj . k∈E (n) (n) Also ist {mj } eine wachsende Folge. Analog folgt, dass {Mj } eine fallende Folge (n) ist. Somit existiert πj = limn Mj . Sei a = inf i,j (P n0 )ij . Dann haben wir (P (n0 +m )ij = X = X (P n0 )ik (P m )kj k∈E k∈E [(P n0 )ik − a(P m )jk ](P m )kj + a X (P m )jk (P m )kj k∈E X = [(P n0 )ik − a(P m )jk ](P m )kj + a(P 2m )jj . k∈E 130 8. MARKOVKETTEN Wir erhalten also (m) (P (n0 +m )ij ≥ mj X (m) [(P n0 )ik − a(P m )jk ] + a(P 2m )jj = mj (1 − a) + a(P 2m )jj k∈E (n +m) (m) (n0 +m) und damit mj 0 ≥ mj (1 − a) + a(P 2m )jj . Analog folgt Mj a) + a(P 2m )jj . Die Differenz wird (n0 +m) Mj (n0 +m) − mj (m) ≤ (1 − a)(Mj (m) ≤ Mj (1 − (m) − mj ) , und damit (kn0 +m) Mj (kn0 +m) − mj (m) ≤ (1 − a)k (Mj (kn +m) (m) − mj ) . (kn +m) gegen Null konvergiert. Somit − mj 0 Lassen wir k → ∞, folgt dass Mj 0 P (n0 ) n ≥ a, ist πj > 0. Aus j (P n )ij = 1, folgt konvergiert (P )ij gegen πj . Da mj P P n n+1 are )ij = dass k∈E (P )ik pkj folgt, dass {π} eine station¨ j πj = 1. Aus (P Verteilung ist.  Die Situation wird komplizierter, falls I = ∞. Wir sagen, die Markovkette ist transient, falls jeder Zustand nur endlich oft besucht wird, und rekurrent, falls jeder Zustand unendlich oft besucht wird. Wir sagen, die Markovkette ist positiv rekurrent, falls die mittlere R¨ uckkehrzeit endlich ist, und Null-rekurrent, falls die mittlere R¨ uckkehrzeit unendlich ist. (n) Wir bezeichnen nun mit fij = IIP[Xk 6= j, 1 ≤ k < n, Xn = j | X0 = i] die (n) Wahrscheinlichkeit, dass der erste Besuch in j zur Zeit n stattfindet, und fj = P (n) (n) fjj . Wir setzen fij = ∞ n=1 fij , und bemerken, dass fij > 0, da die Markovkette irreduzibel ist. Analog ist fj = fjj . Die mittlere R¨ uckkehrzeit bezeichnen wir mit P (n) µj = n nfj . Seien nun i, j ∈ IIN mit i 6= j und N = inf{n : (P n )ij > 0} und M = inf{n : (P n )ji > 0}. Dann haben wir (P n+N +M )ii ≥ (P N )ij (P n )jj (P M )ji . (8.1) P Falls nun j ein rekurrenter Zustand ist, dann ist n (P n )jj = ∞ (Borel–Cantelli). P Somit schliessen wir, dass auch n (P n )ii = ∞. W¨are nun i ein transienter Zustand, so w¨are die Anzahl der Besuche in i geometrisch verteilt, und ∞ ∞ ∞ hX X X (P n )ii = IIE[1IXn =i | X0 = i] = IIE 1IXn =i n=1 n=1 n=1 i X = i <∞ 0 8. MARKOVKETTEN 131 w¨ urde folgen. Wir schliessen aus (8.1), dass alle Zust¨ande der Markovkette transient oder alle Zust¨ande rekurrent sind. Sind die Zust¨ande transient, so folgt daraus, dass (P n )ii gegen Null konvergiert. Da (P n+M )ii ≥ (P n )ij (P M )ji folgt, dass auch (P n )ij gegen Null konvergiert. Wir zeigen nun, dass auch positive Rekurrenz eine Eigenschaft ist, die f¨ ur alle oder keine Zust¨ande der Markovkette gilt. Proposition 8.4. Eine irreduzible und aperiodische Markovkette hat eine der folgenden Eigenschaften: i) Die Zust¨ande sind transient. In diesem Fall gilt limn (P n )ij = 0. P n (P ii) Die Zust¨ande sind Null-rekurrent. In diesem Fall gilt limn (P n )ij = 0. n )ij < ∞, und damit P n (P n )ij = ∞, aber iii) Die Zust¨ande sind positiv rekurrent. In diesem Fall gilt limn (P n )ij = µ−1 j . Beweis. Wir haben die Aussage im transienten Fall schon bewiesen. Sei die Mar(n) kovkette daher rekurrent. Sei uij = IIP[Xn = j | X0 = i] = (P n )ij die Wahrschein(0) lichkeit, dass das Ereignis (R¨ uckkehr) zum Zeitpunkt n eintritt. Wir setzen uii = 1. Dann gilt f¨ ur n ≥ 1 n X (k) (n−k) (n) . fi uii uii = k=1 P∞ (k) k=n+1 fi (keine R¨ uckkehr bis zum Zeitpunkt n), so ist Setzen wir nun rn = (k) r0 = 1. Wir haben fi = rk−1 − rk . Die obige Gleichung ist dann (n) r0 uii n X (n−k) (rk−1 − rk )uii = . k=1 Also erhalten wir n X (n−k) rk uii k=0 = n X (n−k) rk−1 uii k=1 = n−1 X (n−1−k) rk uii (0) = r0 uii = 1 . k=0 Die zweitletzte Gleichung folgt, da die Summe nicht von n abh¨angt. Sei nun λi = (n) (n) limn uii . Sei ε > 0. Es gibt ein n0 , so dass f¨ ur alle n ≥ n0 uii < λi + ε. Es gibt ein P (k) (n) n1 ≥ n0 , so dass ∞ < ε. Es gibt ein n > 2n1 , so dass uii > λi − ε. Also k=n1 fi λi − ε < (n) uii < n1 X k=1 (k) (n−k) fi uii + ε ≤ λi + n1 X k=1 (k) (n−k) fi (uii − λi ) + ε < λi + 2ε . 132 8. MARKOVKETTEN P (n−k) Wir schliessen daraus, dass uii nach λi konvergiert. Ist µi = ∞ k=0 rk < ∞, so Pn (n−k) folgt mit beschr¨ankter Konvergenz aus k=0 rk uii = 1, dass λi µi = 1. Also ist Pm P (n−k) −1 λi = µi . Ist µi = ∞, so konvergiert k=0 rk uii nach λi m k=0 rk . Der Grenzwert ist aber durch 1 beschr¨ankt, also ist λi = 0. Aus (8.1) folgt nun, dass entweder alle (P n )jj gegen Null konvergieren, oder alle einen echt positiven Grenzwert haben. Das heisst, dass entweder alle µi = ∞, oder alle µi < ∞. Somit sind alle Zust¨ande gleichzeitig positiv rekurrent oder Null-rekurrent. Im Falle, wo die Zust¨ande Nullrekurrent sind, ist wegen der Ungleichung (P n+N )ii ≥ (P N )ij (P n )ji die Aussage auch bewiesen. Nehmen wir nun an, dass die Zust¨ande alle positiv rekurrent sind. Sei i 6= j. Dann haben wir n X (n) (k) (n−k) uij = fij ujj . k=1 Die Aussage folgt nun mit beschr¨ankter Konvergenz.  Korollar 8.5. F¨ ur eine irreduzible und aperiodische Markovkette gibt es genau dann eine station¨are Verteilung, wenn die Kette positiv rekurrent ist. In diesem Falle ist πk = µ−1 k . Beweis. Nehmen wir an, es gibt eine station¨are Verteilung {πk }. Dann gilt wegen der beschr¨ankten Konvergenz X X X −1 πk = πi (P n )ik = lim πi (P n )ik = πi µ−1 k = µk . n i i i Sei die Markovkette nun positiv rekurrent. Wir schliessen dann mit Hilfe des Lemmas P P n von Fatou, dass k µ−1 k ≤ 1, da k (P )ik = 1. Aus X (P n+1 )ij = (P n )ik P kj , k erkennen wir, dass µ−1 j ≥ X j µ−1 j ≥ P k µ−1 k P kj . Also ist XX j k µk−1 P kj = XX k j µ−1 k P kj = X µ−1 k . k P −1 Somit gilt das Gleichheitszeichen und {(µ−1 are Verteii / k µk )i } ist eine station¨ lung. Wir haben aber bereits gezeigt, dass πk = µ−1  k . Das folgende Resultat wird oft f¨ ur Simulationen verwendet. 8. MARKOVKETTEN 133 Korollar 8.6. F¨ ur eine irreduzible aperiodische Markovkette {Xn } definieren wir Pn (n) −1 ai = n k=1 1IXk =i , die mittlere Anzahl Besuche in i bis zum Zeitpunkt n. Ist die (n) Markovkette positiv rekurrent, dann konvergiert ai nach µ−1 i . Ist die Markovkette (n) transient oder Null-rekurrent, dann konvergiert ai nach 0. Beweis. Die Aussage ist f¨ ur eine transiente Markovkette klar. Sei die Kette also (0) (n) rekurrent. Nehmen wir an, dass wir in i starten. Sei Ti = 0 und Ti die Zeit des n-ten Besuches in i. Dann haben wir n X (n) (j) ai n = 1IXk =i = sup{j : Ti ≤ n} . k=1 (k) Da die Variablen {Ti konvergiert (k−1) − Ti (n) ai n (n) (j) } unabh¨angig sind, konvergiert j −1 Ti (n) (n) ai n + 1 (ai n+1) ai n + 1 Ti nach µi . Also (n) ≤ ai ≤ ai n (n) a Ti i n nach µ−1 i .  Zum Abschluss betrachten wir im Folgenden Markovketten, die nicht irreduzibel sind. Wir k¨onnen dann die Kette in irreduzible Teilketten Cj und transiente Zust¨ande T zerlegen. Falls X0 = i ein rekurrenter Zustand ist, dann sind alle erreichbaren Zust¨ande in der gleichen irreduziblen Teilkette. Nehmen wir nun an, dass X0 = i in der Menge T von transienten Zust¨anden ist. Dann kann die Markovkette irgendwann eine rekurrente Menge Cj erreichen, oder f¨ ur immer in der Menge T bleiben. Wir wollen nun die Wahrscheinlichkeit xij berechnen, dass die Markovkette in der Menge Cj absorbiert wird. (1) Die Wahrscheinlichkeit im ersten Schritt in die Menge Cj zu gelangen ist xij = k∈Cj Pik . Falls die Kette nicht schon im ersten Schritt in Cj landet, muss sie in T landen, da sonst Cj nicht mehr erreicht werden kann. Daher l¨ost xij das Gleichungssystem X X xij = Pik + Pik xkj . (8.2) P k∈Cj k∈T Falls dieses Gleichungssystem eine eindeutige beschr¨ankte L¨osung hat, sind die {xij } bestimmt. Ansonsten definieren wir X (n+1) (n) xij = Pik xkj , k∈T die Wahrscheinlichkeit, in n + 1 Schritten die Menge Cj zu erreichen. Wir haben P (n) dann xij = ∞ n=1 xij . 134 8. MARKOVKETTEN Betrachten wir nun die Wahrscheinlichkeit yi , dass das System f¨ ur immer in den transienten Zust¨anden bleibt. Dann muss im ersten Schritt ein transienter Zustand erreicht werden. Das heisst, {yi } l¨ost das Gleichungssystem yi = X Pik yk . k∈T Falls 0 die einzige beschr¨ankte L¨osung des obigen Gleichungssystems ist, folgt dass irgend einmal ein rekurrenter Zustand erreicht wird. Falls die L¨osung nicht einP (1) deutig ist, setzen wir yi = k∈T Pik , die Wahrscheinlichkeit, dass die transienten P (n+1) (n) Zust¨ande im ersten Schritt nicht verlassen werden, und yi = k∈T Pik yk die Wahrscheinlichkeit, dass in n + 1 Schritten die transienten Zust¨ande nicht verlassen (n) werden. Dann ist yi = limn yi . Sei nun {zk } eine beschr¨ankte L¨osung des Gleichungssystems zi = X Pik zk . (8.3) k∈T (1) Wir k¨onnen annehmen, dass |zi | ≤ 1. Dann erhalten wir |zi | ≤ yi , und rekursiv, (n) ur immer in |zi | ≤ yi . Also ist |zi | ≤ yi . Wir schliessen somit, dass das System f¨ den transienten Zust¨anden bleiben kann, falls es eine beschr¨ankte L¨osung des Gleichungssystems (8.3) mit zi 6= 0 gibt. In diesem Falle ist {yi } die maximale L¨osung, die durch 1 begrenzt ist. Ist 0 die einzige L¨osung, dann sind die Wahrscheinlichkeiten {xij } durch die eindeutige L¨osung des Systems (8.2) gegeben. Die Differenz zweier L¨osungen von (8.2) l¨ost (8.3). Wir sehen nun auch, dass (8.2) genau dann eine eindeutige beschr¨ankte L¨osung besitzt, falls das System fast sicher einen rekurrenten Zustand erreicht. Ansonsten m¨ ussen wir die Kette unter der Bedingung betrachten, dass das System irgendwann einen rekurrenten Zustand erreicht. Das heisst, wir setzen f¨ ur i ∈ T P˜ik = (1 − yk )Pik /(1 − yi ) , P˜ik = Pik /(1 − yi ) , k∈T , k∈ /T . Dann hat das Gleichungssystem x˜ij = X k∈Cj P˜ik + X P˜ik x˜kj k∈T eine eindeutige beschr¨ankte L¨osung. Die gesuchte L¨osung ist dann xij = x˜ij (1 − yi ). 8. MARKOVKETTEN 135 Beispiel 8.7. Die Matrix P ist gegeben durch P00 = 1 und Pn(n+1) = 1 − Pn0 = pn > 0, n ≥ 1. Dann ist 0 ein rekurrenter Zustand, die andern Zust¨ande sind transient. Wir m¨ ussen dann also das System yn = pn yn+1 l¨osen. Dies hat nur dann eine Qn −1 nicht-triviale L¨osung, falls y1 6= 0. Wir erhalten nun yn+1 = p−1 n yn = y1 k=1 pk . Es Q∞ gibt somit genau dann eine beschr¨ankte L¨osung, falls p = k=1 pk > 0. Da yn ≤ 1, Q folgt y1 ≤ n−1 osung suchen, ist y1 = p, k=1 pk , also y1 ≤ p. Da wir die maximale L¨ Qn−1 Q∞ und damit yn = p/ k=1 pk = k=n pk . Q Setzen wir zum Beispiel pn = n/(n+1), so ist nk=1 pk = 1/(n+1) und konvergiert nach Null. Die Markovkette wird also fast sicher den Zustand 0 erreichen. Setzen Q n n+2 , so ist nk=1 pk = (n + 2)/(2(n + 1)). Dies wir pn = ((n + 1)2 − 1)/(n + 1)2 = n+1 n+1 konvergiert nach p = 21 . Somit ist es m¨oglich, dass die Kette immer in den transienten Zust¨anden verbleibt. Die gesuchte Wahrscheinlichkeit ist dann also yn = n/(n + 1).  Wir k¨onnen nun auch ein Kriterium formulieren, wann eine irreduzible Markovkette transient oder rekurrent ist. Korollar 8.8. Eine irreduzible Markovkette ist genau dann transient, falls das Gleichungssystem ∞ X yi = Pij yj j=1 eine nicht triviale beschr¨ankte L¨osung besitzt. Beweis. F¨ ur eine irreduzible Markovkette m¨ ussen alle Zust¨ande transient oder alle rekurrent sein. Die Kette ist genau dann transient, wenn es einen Zustand gibt, ¨ von dem aus 0 mit echt positiver Wahrscheinlichkeit nicht erreicht wird. Andern wir die Markovkette, so dass 0 absorbierend wird, dann ist die Kette genau dann transient, wenn die Kette die transienten Zust¨ande der ver¨anderten Kette mit positiver Wahrscheinlichkeit nie verl¨asst. Dies ist genau dann der Fall, wenn die obige Gleichung eine nicht triviale beschr¨ankte L¨osung besitzt.  Beispiel 8.2 (Fortsetzung). Im betrachteten Beispiel m¨ ussen wir die Gleichungen y1 = py2 , yk = pyk+1 + (1 − p)yk−1 , k ≥ 2 l¨osen. Ist y1 = 0, so erhalten wir durch Induktion yk = 0 f¨ ur alle k. Somit muss y1 6= 0 gelten, falls eine nichtriviale L¨osung existiert. Wir k¨onnen y1 = 1 w¨ahlen. Dann ist y2 = p−1 . Im Falle p = 21 ist dies y2 = 2. Aus yk+1 = 2yk − yk−1 erhalten wir mittels Induktion yk = k. Somit ist diese 136 8. MARKOVKETTEN L¨osung nicht beschr¨ankt, und die Kette ist rekurrent. Ist p 6= 21 , dann ist die L¨osung yk =  p  1 − p k −1 . 1 − 2p p Diese L¨osung ist genau dann beschr¨ankt, falls p > 12 . Somit ist die Markovkette transient im Falle p > 12 , und rekurrent im Falle p ≤ 12 . Wir haben bereits gesehen, dass nur im Falle p < 12 eine station¨are Verteilung existiert. Also ist die Markovkette positiv rekurrent, falls p < 12 , und Null-rekurrent, falls p = 12 .  Nehmen wir an, wir wissen, dass Xn = i. Sei m < n. Dann ist P m n−m )ji k (P )kj (P k νP qij (n, m) = IIP[Xm = j | Xn = i] = . n k νk (P )ki Insbesondere f¨ ur m = n − 1 erhalten wir P νk (P n−1 )kj P ji kP qij (n, n − 1) = . n k νk (P )ki Wenn das System im station¨aren Zustand startet, dann ist νk = πk = µ−1 k . Dies macht nur Sinn, falls der Prozess positiv rekurrent ist. In diesem Falle erhalten wir qij = qij (n, n − 1) = πj P ji . πi ¨ Die bedingten Wahrscheinlichkeiten qij definieren die Ubergangswahrscheinlichkeiten einer Markovkette. Wir erhalten damit den Prozess, wenn die Zeit umgekehrt wird. Falls wir die gleiche Markovkette erhalten, das heisst, qij = Pij , so nennen wir die Markovkette reversibel. 8.2. Homogene Markovketten in stetiger Zeit Generell definieren wir einen Markovprozess in stetiger Zeit als einen Prozess mit der Eigenschaft IIP[Xt+s ∈ B | Ft ] = IIP[Xt+s ∈ B | Xt ]. Der Prozess heisst homogen, falls IIP[Xt+s ∈ B | Xt = x] = IIP[Xs ∈ B | X0 = x]. Falls der Prozess nur Werte in IIN annimmt, dann darf die Zeit T1 , bis der Prozess den Zustand X0 = i verl¨asst, kein Ged¨achtnis haben. Das heisst sie muss exponentialverteilt sein. Nennen wir den Parameter −Qii . Die Folge der Zust¨ande, die der Prozess besucht, m¨ ussen dann eine ¨ Markovkette bilden. Nennen wir die Ubergangsmatrix P . Es gilt dann Pii = 0, da die Kette den Zustand i verl¨asst. Wir definieren nun Qij = −Pij Qii f¨ ur i 6= j. Die 8. MARKOVKETTEN 137 Matrix Q = (Qij ) heisst Intensit¨ atsmatrix der Markovkette X. Die Matrix Q hat dann die Eigenschaft, dass die Zeilen sich zu Null addieren, die Diagonalen negativ sind, und die Eintr¨age ausserhalb der Diagonalen positiv sind. Wir nehmen an, dass in endlicher Zeit nur endlich viele Spr¨ unge stattfinden k¨onnen. Wir haben nun die Wahrscheinlichkeiten IIP[T1 ≤ h, XT1 = j | X0 = i] = Pij (1 − eQii h ) = Pij (−Qii h + o(h)) = Qij h + o(h) . Also ist Qij die Intensit¨at eines Sprunges von i nach j. Wir wollen nun die Verteilung von Xt bestimmen. Sei pi (t) = IIP[Xt = i]. Wir haben dann pi (t + h) = pi (t)(1 + Qii h) + X pj (t)Qji h + o(h) = pi (t) + X pj (t)Qji h + o(h) . j j6=i Somit sind die Funktionen pi (t) rechtsstetig. Wir haben nun pi (t + h) − pi (t) X = pj (t)Qji + o(1) , h j P also p0i (t) = j pj (t)Qji . Ersetzen wir t durch t − h, erhalten wir die gleiche Differentialgleichung f¨ ur die Ableitung von links. Die L¨osung mit der Anfangsbedingung pi (0) = νi ist (IIP[Xt = i])i = νeQt . Ist der Zustand j vom Zustand i aus erreichbar, dann ist IIP[Xt = j | X0 = i] > 0 f¨ ur alle t, da die Sprungzeiten absolutstetig mit Tr¨ager [0, ∞] sind. Also sind i und j in derselben irreduziblen Menge, falls beide (eQ )ij > 0 und (eQ )ji > 0. Da die Zeiten zwischen Spr¨ ungen exponentialverteilt sind, ist jede irreduzible Markovkette in stetiger Zeit aperiodisch. Wir haben also folgende m¨oglichen irreduziblen Markovketten. Proposition 8.9. Eine irreduzible Markovkette in stetiger Zeit hat eine der folgenden Eigenschaften: i) Die Zust¨ande sind transient. In diesem Fall gilt und limt→∞ etQ = 0. nhQ )ij n (e P ii) Die Zust¨ande sind Null-rekurrent. In diesem Fall gilt h > 0, aber limt→∞ etQ = 0. < ∞ f¨ ur alle h > 0, nhQ )ij n (e P = ∞ f¨ ur jedes 138 8. MARKOVKETTEN iii) Die Zust¨ande sind positiv rekurrent. In diesem Fall gilt limt→∞ (etQ )ij = µ−1 j , wobei µj = IIE[inf{t : Xt = j, Xt− 6= j} | X0 = j] die mittlere R¨ uckkehrzeit nach j ist. Beweis. Die Aussagen im transienten und Null-rekurenten Fall sind klar. Wir wissen, dass (enQ )ij gegen eine station¨are Verteilung der Kette {Xn } konvergiert. Dies ist also ein Eigenvektor der Matrix eQ zum Eigenwert 1. Nach dem Perron– Fr¨obenius-Theorem ist dieser Eigenwert einfach. Da 0 = log 1 ein Eigenwert von Q ist, ist dieser Eigenwert auch einfach, und πQ = 0. Somit konvergiert enhQ gegen den gleichen Grenzwert f¨ ur alle h. Aus IIP[Xnh+s = j | X0 = i] ≥ IIP[Xnh = j | X0 = i](1 − eQjj s ) f¨ ur alle s ∈ [0, h), schliessen wir, dass limt (etQ )ij ≥ πj . Aus IIP[Xnh = j | X0 = i] ≥ IIP[Xnh−s = j | X0 = i](1 − eQjj s ) uckkehrzeit folgt schliessen wir, dass auch limt (etQ )ij ≤ πj . Die Interpretation als R¨ analog.  Wir sehen nun also, dass die station¨are Verteilung die normierte L¨osung der Gleichung πQ = 0 ist. Die folgende Aussage folgt wie im Fall der diskreten Zeit. Korollar 8.10. F¨ ur eine positiv rekurrente Markovkette konvergiert Z t (t) −1 aj = t 1IXs =j ds 0 nach πj = µ−1 ur eine Null-rekurrente oder transiente Markovkette konvergiert j . F¨ (t) aj nach 0.