Vom infinitesimalen Erzeuger zur Markovkette

08.01.2016, 20:03

Boipl

Auf diesen Beitrag antworten »

Vom infinitesimalen Erzeuger zur Markovkette

Ich habe ein Problem mit meinem Lieblingsthema "Markovketten".
Die Aufgabe ist von einer Q-Matrix zu Übergangsmatrizen P(t) zu kommen.

Die Summe der Zeilen in Q ist ja immer 0, die Diagonale immer kleiner 0.
Aber wie konstruiere ich P(t)? Hat jemand einen Hinweis für mich, den ein durchschnittlich schlechter Stochastiker auch versteht? smile

smile

In einem Buch hab ich gesehen dass man da mit exponentiellen Verteilungen arbeiten muss, aber das hat mich nur noch mehr verwirrt.

08.01.2016, 20:19

HAL 9000

Auf diesen Beitrag antworten »

Es ist $\begin{align*} P(t) = e^{Qt} \end{align*}$ , wobei da rechts die Matrixexponentialfunktion steht. Und das folgt aus dem für infinitesimal kleine $\begin{align*} \dd t \end{align*}$ gültigen

$\begin{align*} P(\dd t) = I + Q\cdot \dd t \end{align*}$ ,

dabei ist $\begin{align*} I \end{align*}$ die Einheitsmatrix.

09.01.2016, 12:59

Boipl

Auf diesen Beitrag antworten »

Danke für den Hinweis - ich glaub ich komm da jetzt schon eher weiter.

Kennt jemand einen Befehl für R oder Wolframalpha wo ich die e^Qt checken kann? Habs mal bei wolframalpha mit matrixExp{{-3,1,1,1},{1,-3,1,1},{1,1,-3,1},{1,1,1,-3}}, aber das ist ein Blödsinn, genauso wie e^{{-3,1,1,1},{1,-3,1,1},{1,1,-3,1},{1,1,1,-3}} verwirrt

verwirrt

09.01.2016, 13:14

URL

Auf diesen Beitrag antworten »

und was genau ist da Blödsinn?

10.01.2016, 11:49

Boipl

Auf diesen Beitrag antworten »

Nachdem ich mir das ganze Wochenende schon den Kopf zerbreche, werf ich mal ein konkretes Beispiel in den Raum:

Eine Markovkette mit vier Zuständen hat den inf. Erzeuger Q={{-3, 1, 1, 1},{1, -3, 1, 1},{1, 1, -3, 1},{1, 1, 1, -3}}. Gesucht sind die Übergangsmatrizen P(t) und ihren Grenzwert für t->unendlich.

Von der Markovkette (nennen wir sie D) kommt man auf die Übergangsmatrizen indem man die Eigenwerte und Eigenvektoren ausrechnet, außerdem die inverse.

p^t=D*E*D^-1

Also eigentlich sollte mir das halbwegs klar sein, wie ich von einer Markovkette dazu kam. Nur der Schritt von Q auf D ist mir noch nicht gelungen, trotz Hinweis. Hat vielleicht wer ein kleines Beispiel in der Schublade wie ich diesen Schritt richtig mache?

Bei Wolframalpha bekomme ich mit matrixExp{{-3,1,1,1},{1,-3,1,1},{1,1,-3,1},{1,1,1,-3}} eine Lösung, "zu Fuß" komm ich dort nicht hin.

10.01.2016, 12:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Boipl
Von der Markovkette (nennen wir sie D) kommt man auf die Übergangsmatrizen indem man die Eigenwerte und Eigenvektoren ausrechnet, außerdem die inverse.

p^t=D*E*D^-1

Eine Menge Halbwahrheiten, die du hier verbreitest, begleitet von einer chaotischen Symbolik (D ist bei dir sowohl die Markovkette als auch die Transformationsmatrix der Diagonalisierung ??? ).

Wie oben schon erwähnt, ist $\begin{align*} P(t) = e^{Qt} \end{align*}$ , bleibt "nur" noch die Frage, wie man das im konkreten Fall berechnet. Diagonalisierung ist das richtige Stichwort: Existiert eine Diagonalmatrix $\begin{align*} \Lambda \end{align*}$ und eine Transformationsmatrix $\begin{align*} T \end{align*}$ mit $\begin{align*} Q=T\Lambda T^{-1} \end{align*}$ , so gilt dann $\begin{align*} e^{Qt} = Te^{\Lambda t} T^{-1} \end{align*}$ . Dabei ist $\begin{align*} e^{\Lambda t} \end{align*}$ wieder eine Diagonalmatrix, die auf der Diagonalen die Werte $\begin{align*} e^{-\lambda_k t} \end{align*}$ stehen hat, wobei $\begin{align*} \lambda_1,\ldots,\lambda_n \end{align*}$ die Eigenwerte von Q sind in der Reihenfolge, wie sie in $\begin{align*} \Lambda \end{align*}$ auf der Diagonalen stehen.

Anzeige

10.01.2016, 13:01

URL

Auf diesen Beitrag antworten »

Ich habe keine Ahnung von Markovketten. Wenn ich die vorherigen Posts richtig verstehe, musst du $\begin{eqnarray*} e^{Qt} \end{eqnarray*}$ berechnen. Dazu bestimmt man die Zerlegung $\begin{eqnarray*} Q=SDS^{-1} \end{eqnarray*}$ . D ist eine Diagonalmatrix mit den EW von Q, S enthält die zugehörigen EV.
Der erste Schritt ist also Bestimmung dieser EW und EV
Dann ist $\begin{eqnarray*} e^{Qt}=\sum \frac{t^k}{k!}Q^k=\sum \frac{t^k}{k!}SD^kS^{-1}=S\left(\sum \frac{t^k}{k!}D^k\right)S^{-1} \end{eqnarray*}$
Edit: Zu langsam. Und wech Wink

Wink

10.01.2016, 13:08

Boipl

Auf diesen Beitrag antworten »

Hm, bei euch ist das irgendwie besser erklärt als in meinem sehr rudimentären Skriptum... ich werd gleich mal rechnen und euch meine Lösung voller Stolz präsentieren.... stay tuned.... Augenzwinkern

Augenzwinkern

10.01.2016, 17:09

Boipl

Auf diesen Beitrag antworten »

So, jetzt poste ich mal einen Lösungsvorschlag.

Q= $\begin{eqnarray*} \begin {pmatrix} -3 & 1 & 1 & 1\\ 1 & -3 & 1 & 1 \\ 1 & 1 & -3 & 1 \\ 1 & 1 & 1 & -3 \end{pmatrix} \end{eqnarray*}$

Eigenwerte:
$\begin{eqnarray*} \lambda 1 = -4<br /> \lambda 2 = -4<br /> \lambda 3 = -4<br /> \lambda 4 = 0<br /> \end{eqnarray*}$

S = Transformationsmatrix

$\begin{eqnarray*} S = \begin {pmatrix} -1 & -1 & -1 & 1\\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} <br /> S\textsuperscript{-1} = \begin {pmatrix} -1 & -1 & -1 & 1\\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} <br /> e\textsuperscript{Dt} = \begin {pmatrix} e\textsuperscript{-4t} & 0 & 0 & 0\\ 0 & e\textsuperscript{-4t} & 0 & 0 \\ 0 & 0 & e\textsuperscript{-4t} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}<br /> \end{eqnarray*}$

$\begin{eqnarray*} <br /> P(t) = e\textsuperscript{Qt} = 1/4 e\textsuperscript{-4t} * \begin {pmatrix} 3 & -1 & -1 & -1\\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix} \end{eqnarray*}$

Meiner Meinung nach schaut das gut aus bis daher, allerdings steht in der Angabe etwas von Übergangmatrizen, also Mehrzahl traurig

traurig

Mein Ansatz wäre jetzt
$\begin{eqnarray*} p\textsuperscript{t} = S * I * S\textsuperscript{-1} \end{eqnarray*}$

Würdet ihr das auch so machen? verwirrt

verwirrt

10.01.2016, 17:36

HAL 9000

Auf diesen Beitrag antworten »

Sieht eine ganze Zeit gut aus ... und dann das:

Zitat:

Original von Boipl
$\begin{eqnarray*} <br /> P(t) = e\textsuperscript{Qt} = 1/4 e\textsuperscript{-4t} * \begin {pmatrix} 3 & -1 & -1 & -1\\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix} \end{eqnarray*}$

Erstaunt1

Das ist offensichtlich Unfug - das ist ja nicht mal eine stochastische Matrix (Spaltensumme 1). unglücklich

unglücklich

EDIT: $\begin{align*} S^{-1} \end{align*}$ ist sicher auch falsch.

10.01.2016, 17:58

Boipl

Auf diesen Beitrag antworten »

Oh, Hoppla, ich hab die Inverse falsch abgetippt... die müsste jetzt stimmen. Der Rest muss auch stimmen, ich find sonst keinen Fehler, ich glaube nur es ist die halbe Lösung. Irgendeine Zweite Matrix fehlt da noch, die addiert wird (zumindest bilde ich mir ein sowas in der Vorlesung aufgeschnappt zu haben)
Die Spaltensummen ergeben bei meiner (Teil?-)Lösung genau 0. Das kann ja kein Zufall sein Augenzwinkern

Augenzwinkern

Q= $\begin{eqnarray*} \begin {pmatrix} -3 & 1 & 1 & 1\\ 1 & -3 & 1 & 1 \\ 1 & 1 & -3 & 1 \\ 1 & 1 & 1 & -3 \end{pmatrix} \end{eqnarray*}$

Eigenwerte:
$\begin{eqnarray*} \lambda 1 = -4<br /> \lambda 2 = -4<br /> \lambda 3 = -4<br /> \lambda 4 = 0<br /> \end{eqnarray*}$

S = Transformationsmatrix

$\begin{eqnarray*} S = \begin {pmatrix} -1 & -1 & -1 & 1\\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} <br /> S\textsuperscript{-1} = 1/4 * \begin {pmatrix} -1 & -1 & -1 & 3\\ -1 & -1 & 3 & -1 \\ -1 & 3 & -1 & -1 \\ 1 & 1 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} <br /> e\textsuperscript{Dt} = \begin {pmatrix} e\textsuperscript{-4t} & 0 & 0 & 0\\ 0 & e\textsuperscript{-4t} & 0 & 0 \\ 0 & 0 & e\textsuperscript{-4t} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}<br /> \end{eqnarray*}$

$\begin{eqnarray*} <br /> P(t) = e\textsuperscript{Qt} = 1/4 * e\textsuperscript{-4t} * \begin {pmatrix} 3 & -1 & -1 & -1\\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix} \end{eqnarray*}$

Meiner Meinung nach schaut das gut aus bis daher, allerdings steht in der Angabe etwas von Übergangmatrizen, also Mehrzahl traurig

traurig

Mein Ansatz wäre jetzt
$\begin{eqnarray*} p\textsuperscript{t} = S * I * S\textsuperscript{-1} \end{eqnarray*}$

Würdet ihr das auch so machen?

10.01.2016, 18:29

Boipl

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} p\textsuperscript{t} = S * I * S\textsuperscript{-1} \end{eqnarray*}$

Hm, ich hab mir mal ähnliche Beispiele angesehen, die auf die t-stufige Übergangsmatrizen und den Grenzwert $\begin{eqnarray*} t -> \infty \end{eqnarray*}$ berechnen.
Da wird gerechnet mit $\begin{eqnarray*} p\textsuperscript{t} = S * D * S\textsuperscript{-1} \end{eqnarray*}$ , wobei eben in D die Eigenwerte in der Diagonalen immer mit ^t gerechnet wird (oft wird auch statt t ein n verwendet, wir verwenden halt immer t).

Die Frage ist, ob (und wenn ja: wie) ich die Methode auch bei meinem Beispiel (es ist ja Q gegeben, keine "normale" Übergangsmatrix (wo jede Zeilen- und Spaltensumme gleich eins ist) anwenden kann?

10.01.2016, 18:36

HAL 9000

Auf diesen Beitrag antworten »

Es fehlt ein entscheidender Summand zu deinem Ergebnis: Eine Einheitsmatrix der Dimension 4, nur so wird das ganze überhaupt zu einer stochastischen Matrix (nichtnegative Einträge; Spaltensumme=1). Eigentlich kommt das automatisch raus, wenn du korrekt $\begin{align*} S\cdot e^{Dt}\cdot S^{-1} \end{align*}$ rechnest - ich weiß nicht, warum du die Einheitsmatrix als Summand (erneut) weglässt. unglücklich

unglücklich

EDIT: Ach je, nicht nur der Summand, auch das Gesamtvorzeichen vor der Matrix ist ja falsch. Hab ich mich verkuckt, damit gebe ich den Rettungsversuch auf. Rechne einfach konsequent $\begin{align*} S\cdot e^{Dt}\cdot S^{-1} \end{align*}$ aus, dann erübrigt sich weiteres Gewurstel.

10.01.2016, 19:10

Boipl

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Es fehlt ein entscheidender Summand zu deinem Ergebnis: Eine Einheitsmatrix der Dimension 4, nur so wird das ganze überhaupt zu einer stochastischen Matrix (nichtnegative Einträge; Spaltensumme=1). Eigentlich kommt das automatisch raus, wenn du korrekt $\begin{align*} S\cdot e^{Dt}\cdot S^{-1} \end{align*}$ rechnest - ich weiß nicht, warum du die Einheitsmatrix als Summand (erneut) weglässt. unglücklich

unglücklich

EDIT: Ach je, nicht nur der Summand, auch das Gesamtvorzeichen vor der Matrix ist ja falsch. Hab ich mich verkuckt, damit gebe ich den Rettungsversuch auf. Rechne einfach konsequent $\begin{align*} S\cdot e^{Dt}\cdot S^{-1} \end{align*}$ aus, dann erübrigt sich weiteres Gewurstel.

Hm, das mit dem Summanden verwirrt mich gerade.

Ich hab in der Zwischenzeit mal die Rechnung durch wolframalpha gejagt:

{{-1,-1,-1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}*{{e^(4t),0,0,0},{0,e^(4t),0,0},{0,0,e^(4t),0},{0,0,0,0}}*(1/4*{{-1,-1,-1,3},{-1,-1,3,-1},{-1,3,-1,-1},{1,1,1,1}})

Da wird mein Ergebnis unterstützt, aber ich versteh das Argument, dass das keine stochastische Matrix sein kann.

EDIT: Danke für die bisherige Hilfe! Ich hab bei dem Thema echt so meine Schwierigkeiten wie man sieht Hammer

Hammer

10.01.2016, 19:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Boipl
Ich hab in der Zwischenzeit mal die Rechnung durch wolframalpha gejagt:

{{-1,-1,-1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}*{{e^(4t),0,0,0},{0,e^(4t),0,0},{0,0,e^(4t),0},{0,0,0,0}}*(1/4*{{-1,-1,-1,3},{-1,-1,3,-1},{-1,3,-1,-1},{1,1,1,1}})

Da steht nicht 0, sondern 1.

Und natürlich überall $\begin{align*} e^{-4t} \end{align*}$ , wo bei dir $\begin{align*} e^{4t} \end{align*}$ steht.

10.01.2016, 19:22

Boipl

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Boipl
Ich hab in der Zwischenzeit mal die Rechnung durch wolframalpha gejagt:

{{-1,-1,-1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}}*{{e^(4t),0,0,0},{0,e^(4t),0,0},{0,0,e^(4t),0},{0,0,0,0}}*(1/4*{{-1,-1,-1,3},{-1,-1,3,-1},{-1,3,-1,-1},{1,1,1,1}})

Das steht nicht 0, sondern 1.

Und natürlich überall $\begin{align*} e^{-4t} \end{align*}$ , wo bei dir $\begin{align*} e^{4t} \end{align*}$ steht.

Danke für die Korrektur, das mit dem 0er statt dem 1er war dumm.

Und beim Minus war ich mir nicht sicher, aber ja eigentlich macht das mehr Sinn.
Wenn ich das jetzt ausrechnen lasse, ergibt das aber noch immer keine stochastische Matrix.

10.01.2016, 19:24

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Boipl
Wenn ich das jetzt ausrechnen lasse, ergibt das aber noch immer keine stochastische Matrix.

Du nervst langsam mit deinen dauernden Schusslichkeitsfehlern: Richtig gerechnet ist es eine stochastische Matrix. Forum Kloppe

Forum Kloppe

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »