Markov-Kette < stoch. Prozesse < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe eine Verständnisfrage, die ich für ein aktuelles Problem schnell lösen muss.
Ich habe eine große Übergangsmatrix (mit über 2000 Zeilen). Ich kenne den Anfangszustand, der ist (0,...,0,1). Und ich möchte berechnen, wie groß die Wahrscheinlichkeit ist zur Zeit t zum ersten Mal im Zustand (1,0,...,0) zu sein.
Ich habe folgendes getan. Ich habe die letzte Zeile der Übergangsmatrix als Ausgang genommen, habe diese mit der Übergangsmatrix P multipliziert, und habe in der so erhaltenen Zeile alle Wahrscheinlichkeiten aufsummiert die nicht zum Zustand (1,0,...,0) führen. Diese Zeile entspricht doch den Wahrscheinlichkeiten der Übergänge vom Ausgangszustand in zwei Zeitschritten, oder?
Diese Wahrscheinlichkeit sei [mm] q^{(t)}, [/mm] die ich für die Wahrscheinlichkeit halte zum Zeitpunkt t nicht in den Zielzustand einzutreten.
Dann dachte ich, die Ersteintrittswahrscheinlichkeit Q(t) zur Zeit t würde sich ergeben durch
[mm] Q(t)=\produkt_{i=1}^{t-1} q^{(i)} [/mm] * [mm] (1-q^{(t)}).
[/mm]
Wenn ich mit diesen Q(t) den erwarteten Ersteintrittszeitpunkt berechne, ist dieser aber deutlicher niedriger als der Mittelwert meiner Simulationen.
Und die Abweichung ist immens... Es handelt sich bei den Mittelwerten um Vielfache der berechneten Werte.
Wo ist mein Fehler? Ich dachte erst an Probleme durch Rundungsfehler, doch die berechneten Stationären Verteilung durch wiederholtes Quadrieren der Matrizen liefern korrekte Ergebnisse.
Es muss also an meiner Berechnung etwas falsch sein.
Viele Grüße,
BertanARG
|
|
| |
|
Erstmal eine Anmerkung: Die deutsche Transkription ist Markow-Kette. Hilft manchmal beim Suchen.
Zum Thema: Du sprichst vom (Anfangs-)Zustand als Vektor und von Wahrscheinlichkeiten. Aber eigentlich geht doch eine (Anfangs-)Verteilung in die MK ein. Suchst du die Anzahl der Schritte bis zur hier als Vektor gegebenen Endverteilung? Die hat aber nichts mit dem Zufall zu tun, sondern ist reine lineare Algebra: Übergangsmatrizen multiplizieren bis es passt. Was anderes wäre die Betrachtung der Übergangswahrscheinlichkeiten [mm]p^k_{n1} := M^k(n,1)[/mm] zur Übergangsmatrix M. Für Bezeichnungen siehe ![[]](/images/popup.gif) hier.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:09 Do 19.07.2007 | | Autor: | BertanARG |
Hi,
okay, habe mich nicht so präzise ausgedrückt. I={1,2,...,n} Zustandsraum.
Die Anfangsverteilung sei [mm] \pi_0=(0,...,0,1). [/mm] Das heißt die Markov-Kette startet mit [mm] X_0=n.
[/mm]
Gesucht ist nun die Ersteintrittswahrscheinlichkeit in den Zustand i=1.
Also [mm] P1_N:=P(X_{N}=1 [/mm] | [mm] N=\inf\{t:X_t=1\}).
[/mm]
Mithilfe dieser Wahrscheinlichkeit will ich die Erwartete Ersteintrittszeit berechnen, mithilfe der folgenden Formel
E [mm] [N=\inf\{t:X_t=1\}]=\summe_{t=1}^{\infty} t*P1_t.
[/mm]
Nun dachte ich, ich könnte [mm] P1_N [/mm] berechnen, in dem ich die Übergangsmatrix Q verwende. Sei [mm] \pi_1=(1,0,...,0), \pi_0=(0,...,0,1) [/mm] der Ausgangszustand
Dann ist die Nichteintrittswahrscheinlichkeit q(t) zur Zeit t doch
[mm] q(t)=1-\pi_0*Q^t*\pi_1,
[/mm]
die Eintrittswahrscheinlichkeit zur Zeit t ist
[mm] p(t)=\pi_0*Q^t*\pi_1?
[/mm]
Die Ersteintrittswahrscheinlichkeit [mm] P1_t [/mm] müsste doch dann folgendermaßen berechnet werden können...
[mm] P1_t=p(t)*\produkt_{k=1}^{t-1}q(k)
[/mm]
Dies scheint aber nicht zu stimmen, da der so erhaltene Wert meiner Simulation widerspricht.
Mithilfe des Ansatzes, dass sich E[N] als kleinste Lösung [mm] u_6 [/mm] des LGS
[mm] u_i=1+\summe_{k\not=1}p_{ik}u_k [/mm] ergibt,
erhalte ich zumindest für kleinere Modelle mit n=6 die richtigen Ergebnisse.
Das Lösen von großen LGS ist aber ungleich schwerer, und daher würde ich lieber den Rechenweg oben verwenden. Aber dieser scheint nicht korrekt zu sein, und ich verstehe nicht weswegen.
Um ehrlich zu sein wüsste ich auch gar nicht, wie ich dieses LGS so schreiben kann, dass es mithilfe von Matlab gelöst werden könnte.
Viele Grüße und danke schon mal
|
|
|
| |
|
Seh ich das richtig, dann ist das eigentlich Problem die effiziente Berechnung der potenzierten Übergangsmatrix. Da wäre jetzt die Frage, ob sich die Matrix diagonalisieren lässt, da ja mit [mm]M=T*D*T^{-1}[/mm] gilt: [mm]M^k=T*D^k*T^{-1}[/mm].
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:48 Do 19.07.2007 | | Autor: | BertanARG |
Hallo,
die Berechnungen habe ich bereits durchgeführt. Das Problem ist, dass mein Ansatz nicht das richtig Ergebnis liefert. Und ich verstehe nicht, wieso sich die Erwartete Ersteintrittszeit nicht auf diese Weise berechnen läßt?
Die Markov-Kette ist irreduzibel. Somit wäre sie wohl diagonalisierbar (da eine Stationäre Verteilung eindeutig existieren muss, und das tut sie. Ich habe sie ebenfalls berechnet). Aber wie gesagt, die Berechnungen habe ich bereits durchgeführt. Allerdings sind die Werte, die ich erhalte um ein Vielfaches kleiner als die "echte" Ersteintrittszeit.
Erste Analysen haben ergeben, dass die Ersteintrittswahrscheinlichkeiten sehr schnell (relativ) groß werden. Vermutlich zu früh, sodass hier ein Fehler stecken könnte.
Simulationen des Modells bestätigen im übrigen, dass die von mir verwendete Methode zu kleine Werte liefern muss. Die Berechnung durch Lösen des LGS hingegen liefert realistische Werte.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:53 Do 19.07.2007 | | Autor: | BertanARG |
Hallo nochmal,
mittlerweile wüsste ich auch eine Darstellung des LGS in Matrizenform.
P' gehe durch P hervor in dem die erste Spalte gelöscht wird.
[mm] u=(u_1,...,u_n)^T [/mm] sei ein Zeilenvektor, und [mm] u'=(u_2,...,u_n)^T [/mm] der aus u erstellte Vektor durch Löschen des ersten Eintrags.
[mm] e=(1,...,1)^T [/mm] ein n-dimensionaler Zeilenvektor.
Dann suche ich die Lösung u von u=e+P'*u', genauer gesagt brauche ich nur den Wert [mm] u_n.
[/mm]
|
|
|
| |
|
>Ich habe die letzte Zeile der Übergangsmatrix als Ausgang
> genommen, habe diese mit der Übergangsmatrix P
> multipliziert,
Dann erhältst Du den Vektor der Wahrscheinlichkeiten vom Ausgangszustand aus in einem Schritt zu einem der möglichen Zustände zu gelangen.
> und habe in der so erhaltenen Zeile alle Wahrscheinlichkeiten aufsummiert die nicht zum Zustand (1,0,...,0) führen.
Also dem Zielzustand: dies wäre somit die Wahrscheinlichkeit, vom Anfangszustand in einem Schritt nicht in den Zielzustand zu gelangen, d.h. die Wahrscheinlichkeit [mm] $\mathrm{P}(N_1)$. [/mm] Wobei [mm] $N_k$ [/mm] das Ereignis ist, im Schritt $k$ nicht in den Zielzustand einzutreten.
> Diese Zeile entspricht doch den Wahrscheinlichkeiten der
> Übergänge vom Ausgangszustand in zwei Zeitschritten, oder?
Dies verstehe ich nun leider gar nicht. Aber dies liegt vermutlich an mir.
> Diese Wahrscheinlichkeit sei [mm]q^{(t)},[/mm] die ich für die
> Wahrscheinlichkeit halte zum Zeitpunkt t nicht in den
> Zielzustand einzutreten.
> Dann dachte ich, die Ersteintrittswahrscheinlichkeit Q(t)
> zur Zeit t würde sich ergeben durch
> [mm]Q(t)=\produkt_{i=1}^{t-1} q^{(i)}[/mm] * [mm](1-q^{(t)}).[/mm]
>
> Wenn ich mit diesen Q(t) den erwarteten
> Ersteintrittszeitpunkt berechne, ist dieser aber deutlicher
> niedriger als der Mittelwert meiner Simulationen.
Sicher ist [mm] $Q(t)=\mathrm{P}(N_1\cap N_2\cap \ldots\cap N_{t-1}\cap \overline{N}_t)$. [/mm] Da Du die Wahrscheinlichkeiten aller dieser Teilereignisse multiplizierst (sofern diese $q(i)$ überhaupt die Wahrscheinlickeiten [mm] $\mathrm{P}(N_i)$ [/mm] sind, was ich auch nicht so recht glauben kann), nimmst Du offenbar an, dass diese Ereignisse [mm] $N_1,\ldots, N_t$ [/mm] unabhängig voneinander sind. Aber weshalb sollte diese Annahme richtig sein?
|
|
|
| |
|
Hi,
ich weiß nicht warum diese Frage dämlich sein soll.
[mm] \pi(0)=(0,...,0,1). [/mm] y=(1,0,...,0).
Jedenfalls ist der Hinweis mit der Unahängigkeit sehr gut.
wenn ich [mm] \pi(t)=\pi(0)*Q^t [/mm] betrachte, dann habe ich doch die Wahrscheinlichkeiten wo ich nach t Zeitschritten beginnend von [mm] \pi(0) [/mm] aus sein werden, oder nicht?
[mm] \pi_1(t) [/mm] ist dann die Wahrscheinlichkeit in t Zeitschritten vom Ausgangszustand in den Zustand 1 gelangt zu sein. Folglich muss
[mm] q(t)=1-\pi_1(t) [/mm] die Wahrscheinlichkeit sein, nach t Zeitschritten nicht in den Zustand 1 gelangt sein (oder was ist an dieser Annahme falsch?).
[mm] q(t)=1-\pi(0)*Q^t*y=1-\pi_1(t), [/mm] oder?
Dann wäre meine neue Frage wie ich anhand der Nichteintrittswahrscheinlichkeiten, bzw. anhand der Eintrittswahrscheinlichkeiten die Ersteintrittszeit zum Zeitpunkt t berechnen kann?
[mm] P(N_1 \cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=?
[/mm]
Gilt dann
[mm] P(N_1 \cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=P(N_1)*P(N_2|N_1)*\ldots *P(\overline{N_t}|N_{t-1})?
[/mm]
Die [mm] P(N_i|N_{i-1}) [/mm] ließen sich doch dann gemäß der Bayes-Formel bestimmen, oder?
Also [mm] P(N_i|N_{i-1})=\bruch{P(N_i \cap N_{i-1})}{P(N_{i-1})}. [/mm] Wie könnte ich hier die [mm] P(N_i \cap N_{i-1}) [/mm] berechnen?
|
|
|
| |
|
> Hi,
>
> ich weiß nicht warum diese Frage dämlich sein soll.
> [mm]\pi(0)=(0,...,0,1).[/mm] y=(1,0,...,0).
> Jedenfalls ist der Hinweis mit der Unahängigkeit sehr
> gut.
Jedenfalls gibt es triviale Beispiele, die zeigen, dass solche Unabhängigkeit nicht zu gelten braucht. Etwa dieses (Anfangszustand A, Zielzustand Z):
[Dateianhang nicht öffentlich]
Wenn [mm] $N_2$ [/mm] von [mm] $N_1$ [/mm] unabhängig wäre, müsste ja [mm] $\mathrm{P}(N_2|N_1)=\mathrm{P}(N_2)$ [/mm] sein. Für dieses Beispiel ist aber [mm] $\mathrm{P}(N_2|N_1)=\frac{1}{2}$ [/mm] und [mm] $\mathrm{P}(N_2)=\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{3}=\frac{5}{12}\neq \mathrm{P}(N_2)$
[/mm]
> wenn ich [mm]\pi(t)=\pi(0)*Q^t[/mm] betrachte, dann habe ich doch
> die Wahrscheinlichkeiten wo ich nach t Zeitschritten
> beginnend von [mm]\pi(0)[/mm] aus sein werden, oder nicht?
Ja, denke ich auch - bei passender Interpretation von $Q$. Ich hatte Deine Beschreibung im ursprünglichen Fragetext einfach nicht so interpretiert.
> [mm]\pi_1(t)[/mm] ist dann die Wahrscheinlichkeit in t
> Zeitschritten vom Ausgangszustand in den Zustand 1 gelangt
> zu sein.
Ok
> Folglich muss
> [mm]q(t)=1-\pi_1(t)[/mm] die Wahrscheinlichkeit sein, nach t
> Zeitschritten nicht in den Zustand 1 gelangt sein (oder was
> ist an dieser Annahme falsch?).
Finde ich richtig.
>
> [mm]q(t)=1-\pi(0)*Q^t*y=1-\pi_1(t),[/mm] oder?
Gut.
>
> Dann wäre meine neue Frage wie ich anhand der
> Nichteintrittswahrscheinlichkeiten, bzw. anhand der
> Eintrittswahrscheinlichkeiten die Ersteintrittszeit zum
> Zeitpunkt t berechnen kann?
>
> [mm]P(N_1 \cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=?[/mm]
>
> Gilt dann
> [mm]P(N_1 \cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=P(N_1)*P(N_2|N_1)*\ldots *P(\overline{N_t}|N_{t-1})?[/mm]
Nein, nicht ganz. Es ist meiner Meinung nach:
[mm]\mathrm{P}(N_1\cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=\mathrm{P}(N_1)\cdot \mathrm{P}(N_2|N_1)\cdot \mathrm{P}(N_3|N_1\cap N_2) \cdot \mathrm{P}(N_4|N_1\cap N_2\cap N_3)\cdots \mathrm{P}(\overline{N}_t|N_1\cap N_2\cap \ldots \cap N_{t-1})[/mm]
Denn es ist ja
[mm]\mathrm{P}(N_1\cap N_2 \cap \ldots N_{t-1} \cap \overline{N_t})=\mathrm{P}(N_1\cap N_2\cap \ldots\cap N_{t-1})\cdot \mathrm{P}(\overline{N}_t|N_1\cap N_2 \cap N_{t-1})=\mathrm{P}(N_1\cap N_2\cap \ldots N_{t-2})\cdot \mathrm{P}(N_{t-1}|N_1\cap N_2\cap \ldots N_{t-2})\cdot \mathrm{P}(\overline{N}_t|N_1\cap N_2 \cap N_{t-1}) = \cdots[/mm]
>
> Die [mm]P(N_i|N_{i-1})[/mm] ließen sich doch dann gemäß der
> Bayes-Formel bestimmen, oder?
> Also [mm]P(N_i|N_{i-1})=\bruch{P(N_i \cap N_{i-1})}{P(N_{i-1})}.[/mm]
> Wie könnte ich hier die [mm]P(N_i \cap N_{i-1})[/mm] berechnen?
Die genügen nicht, siehe oben.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Hi,
ja, du hast recht. Ich habe die Wahrscheinlichkeiten falsch bedingt.
[mm] P(N_t) [/mm] ist ja die Wahrscheinlichkeit zur Zeit t nicht im Zielzustand zu sein. Dabei spielt es ja keine Rolle, ob er vorher irgendwann einmal erreicht war.
Daher brauche ich [mm] P(N_t|N_1 \cap N_2 \cap [/mm] ... [mm] \cap N_{t-1}). [/mm] Das sieht mir aber sehr komplex aus, ich bezweifle dass sich dies einfach berechnen läßt, oder?
Irgendeine Idee?
Ansonsten bräuchte ich ein Programm zum Lösen der LGS (siehe Eintrag im Numerik-Forum), mit dem ich die Mittlere Ersteintrittszeit berechnen kann.
Ich erklär mal auch, wofür ich das alles benötige. Ich möchte verschiedene Modelle (durch verschiedene Übergangsmatrizen repräsentiert) in Sachen Geschwindigkeit miteinander vergleichen.
Es geht dabei darum vom Zustand n aus möglichst schnell in den Zustand 1 (bzw. eine Gruppe [mm] J=\{1,...,k\}) [/mm] zu gelangen.
Dafür hätte sich die Ersteintrittszeit natürlich geradezu angeboten. Wenn diese sich aber nicht auf einfachem Wege berechnen läßt, anhand welcher Kenndaten könnte ich die Modelle trotzdem in punkto Geschwindigkeit miteinander vergleichen?
Viele Grüße und danke schon mal
|
|
|
| |
|
> Hi,
>
> ja, du hast recht. Ich habe die Wahrscheinlichkeiten falsch
> bedingt.
> [mm]P(N_t)[/mm] ist ja die Wahrscheinlichkeit zur Zeit t nicht im
> Zielzustand zu sein. Dabei spielt es ja keine Rolle, ob er
> vorher irgendwann einmal erreicht war.
>
> Daher brauche ich [mm]P(N_t|N_1 \cap N_2 \cap[/mm] ... [mm]\cap N_{t-1}).[/mm]
> Das sieht mir aber sehr komplex aus, ich bezweifle dass
> sich dies einfach berechnen läßt, oder?
> Irgendeine Idee?
Wie wärs, wenn Du dem Modell einen weiteren Zustand hinzufügen würdest, der nur vom bisherigen Zielzustand 1 aus erreichbar ist und aus dem das System nicht mehr heraus kann? Dann müsste doch, für das so modifzierte System, [mm] $\pi_1(t)$ [/mm] die gewünschte Wahrscheinlichkeit sein, dass das System zum ersten mal im gewünschten Zielzustand 1 ist (im nächsten Schritt geht es ja dann in den hinzugefügten Zustand über, aus dem es nicht mehr heraus kommt).
Nachtrag: Natürlich darf vom bisherigen Zielzustand 1 kein Übergang zu einem der anderen alten Zustände mehr vorhanden sein. Die Wahrscheinlichkeiten für solche Zustandsübergänge von 1 zu einem der anderen alten Zustände können einfach 0 gesetzt werden, weil sie für die gesuchte Wahrscheinlichkeit des ersten Besuches von 1 nicht relevanten Entwicklungen des Systems entsprechen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:09 Do 19.07.2007 | | Autor: | BertanARG |
Wow,
das ist eine super Idee. Ich werde das gleich einmal testen. Das ist eine dieser simplen Ideen, auf die man aber erst einmal kommen muss.
Danke und viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:04 Do 19.07.2007 | | Autor: | BertanARG |
Hi,
es hat wirklich geklappt. Zuerst dachte ich, es könnte genügen einfach den Zielzustand zu einem absorbierenden zu machen. Das geht aber natürlich nicht, da die Wahrscheinlichkeiten wieder gegen Null gehen müssen.
Dies entspricht nun wirklich der Ersteintrittszeit, und deckt sich gut mit meinen Simulationsergebnissen.
Eine tolle Idee, ich bin wirklich beeindruckt. Die erste Frage könnt ihr jetzt beantworten, oder den Status auf erledigt setzen. Ich kann das irgendwie nicht selbst machen.
Viele Grüße,
BertanARG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:16 Do 19.07.2007 | | Autor: | Somebody |
> Hi,
>
> es hat wirklich geklappt. Zuerst dachte ich, es könnte
> genügen einfach den Zielzustand zu einem absorbierenden zu
> machen. Das geht aber natürlich nicht, da die
> Wahrscheinlichkeiten wieder gegen Null gehen müssen.
Doch etwas in dieser Art geht schon: Nur hat dann die Wahrscheinlichkeit [mm] $\pi_1(t)$ [/mm] des Zielzustandes nach $t$ Schritten eine andere Bedeutung. Deine Wahrscheinlichkeit des ersten Besuches des Zielzustandes nach $t$ Schritten wäre dann einfach [mm] $\pi_1(t)-\pi_1(t-1)$.
[/mm]
In diesem Falle würdest Du also im modifizierten Modell den Zielzustand mit Wahrscheinlichkeit 1 wieder in den Zielzustand, mit Wahrscheinlichkeit 0 in einen der anderen Zustände übergehen lassen.
> Dies entspricht nun wirklich der Ersteintrittszeit, und
> deckt sich gut mit meinen Simulationsergebnissen.
>
> Eine tolle Idee, ich bin wirklich beeindruckt.
Freut mich, dass sie Dir geholfen hat, Dein Problem auf befriedigende Weise zu lösen.
> Die erste
> Frage könnt ihr jetzt beantworten, oder den Status auf
> erledigt setzen. Ich kann das irgendwie nicht selbst
> machen.
|
|
|
| |
|
Dieses Problem ist nach Ansicht des Fragestellers auf befriedigende Weise gelöst (siehe https://www.vorhilfe.de/read?i=284051). Ich schreibe diese Antwort nur, um den Status der Frage auf beantwortet zu setzen.
|
|
|
|
