Theory of Stochastic Signals/Markov Chains

1. Theory of Stochastic Signals
2. Wahrscheinlichkeitsrechnung
3. Markov Chains

• Previous page
• Next page

• Previous page
• Next page

Betrachtetes Szenario

Wir betrachten nun abschließend den Fall, dass man ein Experiment fortlaufend durchführt und zu jedem diskreten Zeitpunkt $ν =$ 1, 2, 3, ….. ein Ereignis $E_ν$ eintritt. Hierbei soll gelten: $$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}...\hspace{0.1cm}, E_\mu , \hspace{0.1cm}...\hspace{0.1cm}, E_M \}.$$

Diese mathematisch nicht ganz saubere Nomenklatur bedeutet (siehe nachfolgende Grafik):

• Die $M$ möglichen Ereignisse werden mit dem Laufindex $μ$ durchnummeriert.
• Der Index $ν$ benennt die diskreten Zeitpunkte, zu denen Entscheidungen gefällt werden.

Zur einfacheren Darstellung beschränken wir uns im Folgenden auf den Fall $M =$ 2 mit der Grundmenge $G$ = { $A, B$}. Wir berücksichtigen, dass die Wahrscheinlichkeit des Ereignisses $E_ν$ durchaus von allen vorherigen Ereignissen – also von $E_{ν–1}, E_{ν–2}, E_{ν–3}$, . . . – abhängen kann. Das bedeutet auch, dass wir eine Ereignisfolge mit inneren statistischen Bindungen betrachten.

Dieses Szenario ist ein Sonderfall eines zeit- und wertdiskreten Zufallsprozesses. Solche Prozesse werden in Kapitel 4.4 noch ausführlich behandelt.

Aus einem Kartenstapel mit 32 Karten (darunter 4 Asse) werden nacheinander Karten gezogen. Mit den Ereignissen $A =$ „die gezogene Karte ist ein Ass” und $B =$ „die gezogene Karte ist kein Ass” lauten die Wahrscheinlichkeiten zum Zeitpunkt $ν =$ 1: $${\rm Pr} (A_{\rm 1}) = \frac{4}{32}= \frac{1}{8}; \hspace{0.5cm}{\rm Pr} (B_{\rm 1}) = \frac{28}{32}= \frac{7}{8}.$$

Die Wahrscheinlichkeit Pr( $A_2$), dass zur Zeit $ν =$ 2 ein Ass gezogen wird, hängt nun davon ab,

• ob zum Zeitpunkt $ν =$ 1 ein Ass gezogen wurde ⇒ Pr( $A_2$) = 3/31 < 1/8, oder
• ob zum Zeitpunkt $ν =$ 1 kein Ass gezogen wurde ⇒ Pr( $A_2$) = 4/31 > 1/8.

Auch die Wahrscheinlichkeiten Pr( $A_ν$) zu späteren Zeitpunkten $ν$ hängen stets vom Eintreffen bzw. Nichteintreffen aller vorherigen Ereignisse $E_1 ... E_{ν–1}$ ab.

Allgemeine Definition einer Markovkette

In Sonderfällen, die allerdings sehr häufig vorkommen, kann das oben beschriebene Szenario durch eine Markovkette beschrieben werden.

Eine Markovkette $k$-ter Ordnung (englisch: Markov Chain) dient als Modell für zeit- und wertdiskrete Vorgänge, bei denen die Ereigniswahrscheinlichkeiten zur Zeit $ν$ von den vorherigen Ereignissen $E_{ν–1}, ... , E_{ν–k}$ abhängen und durch $M^{k+1}$ bedingte Wahrscheinlichkeiten ausgedrückt werden können. Für $M =$ 2 gibt es deshalb $2^{k+1}$ solcher Wahrscheinlichkeiten: $${\rm Pr} ( E_\nu \hspace {0.05cm}| \hspace {0.05cm}E_{\nu {\rm -1 }},\hspace {0.1cm} ...\hspace {0.1cm}, E_{\nu { -k }}) \hspace {0.5cm} {\rm mit}\hspace {0.5cm} E_{\nu }\in \{ A, B \}, \hspace {0.1cm}...\hspace {0.1cm}, E_{\nu { -k }} \in \{ A, B \}.$$

Das nachfolgende Bild verdeutlicht diesen Sachverhalt am Beispiel $k =$ 2.

Natürliche Sprachen sind oft durch Markovketten beschreibbar, wobei allerdings die Ordnung $k$ gegen Unendlich strebt. Nähert man einen Text durch eine Markovkette 2. Ordnung an, so ergibt sich zwar kein sinnvoller Inhalt, aber die Struktur der Sprache ist erkennbar.

Das untere Bild zeigt links einen Text, der ausgehend von einer deutschen Buchvorlage mit Bindungen bis zu zweiter Ordnung synthetisch erzeugt wurde. Beim rechten Text wurde eine englische Vorlage verwendet. Man erkennt trotz der Beschränkung $k =$ 2 viele (kurze) deutsche bzw. englische Wörter und auch, dass deutsche Wörter im Mittel länger sind als englische.

Markovkette erster Ordnung

Im Folgenden beschränken wir uns stets auf den Sonderfall $k =$ 1.

Bei einer Markovkette erster Ordnung (englisch: First Order Markov Chain) werden lediglich die statistische Bindung zum letzten Ereignis berücksichtigt, die in der Praxis meist auch am stärksten ist.

Eine binäre Markovkette ⇒ Grundmenge $G$ = { $A, B$ } weist folgende Wahrscheinlichkeiten auf: $${\rm Pr}(A_\nu) = {\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}) \cdot {\rm Pr}(A_{\nu - 1}) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) ,$$ $${\rm Pr}(B_\nu) = {\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}) \cdot {\rm Pr}(A_{\nu - 1}) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) .$$

Hierzu ist anzumerken:

• Pr( $A_ν$) steht als Abkürzung für die Wahrscheinlichkeit, dass $E_ν = A$ ist.
• Zu jedem beliebigen Zeitpunkt $ν$ gilt: Pr( $B_ν$) = 1 – Pr( $A_ν$).
• Es gibt zu jedem Zeitpunkt vier Übergangswahrscheinlichkeiten Pr( $E_ν | E_{ν–1}$), von denen jedoch nur zwei unabhängig sind, denn es gilt:

$${\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}) = 1 - {\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}), \hspace{0.5cm}{\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}) = 1 - {\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}).$$

• Durch Verallgemeinerung dieser letzten Aussage gelangt man zu dem Ergebnis, dass es bei einer Markovkette mit $M$ Ereignissen zu jedem Zeitpunkt $ν$ genau $M · (M – 1)$ voneinander unabhängige Übergangswahrscheinlichkeiten gibt.

Mit den vorgegebenen Übergangswahrscheinlichkeiten Pr( $A_ν | A_{ν–1}$) = 0.2 und Pr( $B_ν | B_{ν–1}$) = 0.4 sind auch die beiden anderen Übergangswahrscheinlichkeiten festgelegt: Pr( $B_ν | A_{ν–1}$) = 0.8 und Pr( $A_ν | B_{ν–1}$) = 0.6.

Homogene Markovketten

Eine Anwendbarkeit der Markovketten auf praktische Probleme ist meist nicht gegeben, wenn nicht weitere einschränkende Voraussetzungen getroffen werden.

Sind alle Übergangswahrscheinlichkeiten unabhängig vom betrachteten Zeitpunkt $ν$, so bezeichnet man die Markovkette als homogen (englisch: homogeneous). Im Fall $M =$ 2 verwenden wir hierfür folgende Abkürzungen: $${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A) = {\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) = {\rm Pr}(A_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}) ,$$ $${\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) = {\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) = {\rm Pr}(B_\nu \hspace{0.05cm} | \hspace{0.05cm}B_{\nu - 1}) .$$

Damit lauten die beiden Ereigniswahrscheinlichkeiten einer binären homogenen Markovkette, die im Gegensatz zu den bedingten Übergangswahrscheinlichkeiten absolute Wahrscheinlichkeiten darstellen: $${\rm Pr}(A_\nu) = {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A) \cdot {\rm Pr}(A_{\nu - 1}) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) \cdot {\rm Pr}(B_{\nu - 1}) ,$$ $${\rm Pr}(B_\nu) = {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) \cdot {\rm Pr}(A_{\nu - 1}) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) \cdot {\rm Pr}(B_{\nu - 1}) .$$ Diesen Zusammenhang kann man auch aus dem nachfolgend dargestellten Markovdiagramm ablesen. Die Summe der abgehenden Pfeile eines Ereignisses ( $A_ν$ bzw. $B_ν$) ergibt sich stets zu 1.

Sie können das „Einschwingverhalten” der Ereigniswahrscheinlichkeiten einer solchen binären Markovkette mit dem folgenden Interaktionsmodul berechnen und anzeigen lassen:

Stationäre Wahrscheinlichkeiten

Wichtige Eigenschaften von Zufallsprozessen sind Stationarität und Ergodizität (Näheres hierzu im Kapitel 4.4). Hier werden diese Begriffe vorausgreifend auf Markovketten angewandt.

Sind bei einer Markovkette neben den Übergangswahrscheinlichkeiten auch alle Ereigniswahrscheinlichkeiten unabhängig vom Zeitpunkt $ν$, so bezeichnet man sie als stationär (englisch: stationary). Man verzichtet dann auf den Index $ν$ und schreibt im binären Fall: $${\rm Pr}(A_\nu ) = {\rm Pr}(A ) \hspace{0.5 cm} {\rm bzw.} \hspace{0.5 cm} {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$ Diese Größen nennt man auch die ergodischen Wahrscheinlichkeiten der Markovkette.

Stationäre Markovketten weisen die nachfolgend genannten Besonderheiten auf:

• Zur Berechnung der ergodischen Wahrscheinlichkeiten einer binären Markovkette ( $M =$ 2) kann man folgende Gleichungen verwenden:

$${\rm Pr}(A) = {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A) \cdot {\rm Pr}(A) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) \cdot {\rm Pr}(B) ,$$ $${\rm Pr}(B) = {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) \cdot {\rm Pr}(A) \hspace{0.1cm} + \hspace{0.1cm} {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) \cdot {\rm Pr}(B) .$$

• Da diese Gleichungen linear voneinander abhängen, darf man nur eine davon benutzen. Als zweite Bestimmungsgleichung kann man beispielsweise Pr( $A$) + Pr( $B$) = 1 verwenden.
• Aus diesen Gleichungen ergeben sich die ergodischen Wahrscheinlichkeiten zu

$${\rm Pr}(A) = \frac {{\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) }{{\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) }\hspace{0.1cm}, \hspace{0.5cm}{\rm Pr}(B) = \frac {{\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) }{{\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) }.$$

Bei einer stationären Markovkette treten sehr lange nach Einschalten der Kette ( $ν → ∞$) stets die ergodischen Wahrscheinlichkeiten auf, unabhängig von den Startbedingungen Pr( $A_0$) und Pr( $B_0$).

Wir betrachten eine binäre Markovkette mit den beiden Ereignissen $A$ und $B$ und den Übergangswahrscheinlichkeiten Pr( $A | A$) = 0.4 und Pr( $B | B$) = 0.8. Weiterhin setzen wir voraus, dass jede Realisierung dieser Kette zum Startzeitpunkt $ν$ = 0 mit dem Ereignis $A$ beginnt. Man erhält dann die nachfolgend aufgelisteten Ereigniswahrscheinlichkeiten:

Es handelt sich hier im strengen Sinne um eine nichtstationäre Markovkette, die jedoch bereits nach sehr kurzer Zeit (nahezu) eingeschwungen ist. Zu späteren Zeitpunkten ( $ν >$ 5) werden die Ereigniswahrscheinlichkeiten Pr( $A_ν$) ≈ 1/4 und Pr( $B_ν$) ≈ 3/4 nicht mehr gravierend verändert.

Anmerkung: Aus der Angabe Pr( $A_ν=5$) = 0.250 bzw. Pr( $B_ν=5$) = 0.750 sollte nicht geschlossen werden, dass die Markovkette zum Zeitpunkt $ν$ = 5 schon vollkommen eingeschwungen ist. Die exakten Werte sind Pr( $A_ν=5$) = 0.25024 und Pr( $B_ν=5$) = 0.74976.

Matrix-Vektordarstellung (1)

Homogene Markovketten können mit Vektoren und Matrizen sehr kompakt dargestellt werden. Dies empfiehlt sich insbesondere, wenn mehr als zwei Ereignisse betrachtet werden: $$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}...\hspace{0.1cm}, E_\mu , \hspace{0.1cm}...\hspace{0.1cm}, E_M \}.$$ Für die Matrix-Vektorendarstellung verwenden wir folgende Nomenklatur:

• Die $M$ Wahrscheinlichkeiten zum Zeitpunkt $ν$ fasst man zu einem Spaltenvektor zusammen:

$${\mathbf{p}^{(\nu)}} = \left[ \begin{array}{c} {p_{\rm 1}}^{(\nu)} \\ \multicolumn{1}{c} \dotfill \\ {p_{M}}^{(\nu)} \end{array} \right] \hspace{0.5cm}{\rm mit} \hspace{0.5cm} {p_{\mu}}^{(\nu)} = {\rm Pr}(E_\nu = E_\mu ).$$

• Die Übergangswahrscheinlichkeiten werden durch eine $M$ x $M$-Matrix ausgedrückt:

$${\mathbf{P}} =\left( p_{ij} \right) = \left[ \begin{array}{cccc} p_{11} & p_{12} & \cdots & p_{1M} \\ p_{21} & p_{22}& \cdots & p_{2M} \\ \multicolumn{4}{c} \dotfill \\ p_{M1} & p_{M2} & \cdots & p_{MM} \end{array} \right] \hspace{0.5cm}{\rm mit} \hspace{0.5cm} {p_{ij}} = {\rm Pr}(E_{\nu +1 } = E_j \hspace{0.05cm}| \hspace{0.05cm} E_{\nu } = E_i).$$

Die nebenstehende Abbildung verdeutlicht diese Nomenklatur am Beispiel $M =$ 2.

Der neue Ereigniswahrscheinlichkeitsvektor nach einem Schritt lautet: $${\mathbf{p}^{(\nu + 1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(\nu )}} .$$

${\mathbf{P}^{\rm T}}$ bezeichnet hierbei die transponierte Matrix zu P. Nach $n$ Schritten ergibt sich somit $${\mathbf{p}^{(\nu +{\it n})}} = \left( {\mathbf{P}}^{\rm T} \right)^n \cdot {\mathbf{p}^{(\nu )}} .$$

Im Grenzübergang ( $n → ∞$) erreicht man dann stets die Stationarität der Markovkette: $$\lim_{n \to\infty}\hspace{0.1cm}{\mathbf{p}^{(\nu + n)}} = \lim_{n \to\infty} \left( {\mathbf{P}}^{\rm T} \right)^n \cdot {\mathbf{p}^{(\nu )}} = {\mathbf{p}}_{\rm erg}= \left[ \begin{array}{c} {p_{\rm 1}} \\ \multicolumn{1}{c} \dotfill \\ {p_{M}} \end{array} \right] .$$

Die Wahrscheinlichkeiten $p_1, ... , p_M$ werden als die ergodischen Wahrscheinlichkeiten bezeichnet. Multipliziert man die Übergangsmatrix unendlich oft mit sich selbst und benennt das Ergebnis mit ${\mathbf{P}}_{\rm erg}$, so besteht die resultierende Matrix aus $M$ gleichen Spalten: $${\mathbf{P}}_{\rm erg} = \lim_{n \to\infty} {\mathbf{P}}^n = \left[ \begin{array}{cccc} p_{1} & p_{2} & \cdots & p_{M} \\ p_{1} & p_{2}& \cdots & p_{M} \\ \multicolumn{4}{c} \dotfill \\ p_{1} & p_{2} & \cdots & p_{M} \end{array} \right] .$$

Matrix-Vektordarstellung (2)

Wir betrachten eine Markovkette mit den Ereignissen $E_1, E_2$ und $E_3$. Die Grafik zeigt das Markovdiagramm, die Übergangsmatrix P und deren Potenzen. Im Markovdiagramm sind alle Übergangswahrscheinlichkeiten „1/2” blau eingezeichnet; grün kennzeichnet „1/4”.

Beim Start ( $ν =$ 0) sind alle Ereignisse gleichwahrscheinlich. Dann gilt für den Zeitpunkt $ν =$ 1: $${\mathbf{p}^{(1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(0 )}}= \left[ \begin{array}{ccc} 1/2 & 1/2& 1/2 \\ 1/4 & 0 & 1/2 \\ 1/4& 1/2& 0 \end{array} \right] \left[ \begin{array}{c} 1/3 \\ 1/3 \\ 1/3 \end{array} \right] = \left[ \begin{array}{c} 1/2 \\ 1/4 \\ 1/4 \end{array} \right] .$$

Hieraus ist zu ersehen, dass man von der Matrix P durch den Austausch der Zeilen und Spalten zur transponierten Matrix ${\mathbf{P}^{\rm T}}$ kommt. Zum Zeitpunkt $ν =$ 2 (und auch zu allen späteren Zeiten) ergeben sich die gleichen Wahrscheinlichkeiten: $${\mathbf{p}^{(2)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(1 )}}= \left[ \begin{array}{ccc} 1/2 & 1/2& 1/2 \\ 1/4 & 0 & 1/2 \\ 1/4& 1/2& 0 \end{array} \right] \left[ \begin{array}{c} 1/2 \\ 1/4 \\ 1/4 \end{array} \right] = \left[ \begin{array}{c} 1/2 \\ 1/4 \\ 1/4 \end{array} \right] .$$

Das bedeutet: Die ergodischen Wahrscheinlichkeiten sind 1/2, 1/4 und 1/4. Dieses Ergebnis hätte man auch direkt aus der ergodischen Matrix ablesen können: $${\mathbf{P}}_{\rm erg} = \lim_{n \to\infty} {\mathbf{P}}^n = \left[ \begin{array}{ccc} 1/2 & 1/4 & 1/4 \\ 1/2 & 1/4 & 1/4 \\ 1/2 & 1/4 & 1/4 \end{array} \right] .$$

Diese ergibt sich durch fortlaufende Multiplikation der Übergangsmatrix mit sich selbst. Im obigen Bild sind die Potenzen $\mathbf{P}^2$ und $\mathbf{P}^3$ angegeben, die sich der Matrix $\mathbf{P}_{\rm erg}$ annähern.