Difference between revisions of "Theory of Stochastic Signals/Markov Chains"

From LNTwww
 
(19 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
{{Header
 
{{Header
 
|Untermenü=Probability Calculation
 
|Untermenü=Probability Calculation
|Vorherige Seite=Statistical Dependence and Independence
+
|Vorherige Seite=Statistical_Dependence_and_Independence
|Nächste Seite=Wahrscheinlichkeit und relative Häufigkeit
+
|Nächste Seite=From_Random_Experiment_to_Random_Variable
 
}}
 
}}
 
==Considered scenario==
 
==Considered scenario==
 
<br>
 
<br>
WFinally, we consider the case where one runs a random experiment continuously and that at each discrete time&nbsp; $(ν = 1, 2, 3, \text{...})$&nbsp; a new event&nbsp; $E_ν$&nbsp;. Here, let hold:
+
Finally,&nbsp; we consider the case where one conducts a random experiment continuously and that at each discrete time&nbsp; $(ν = 1, 2, 3, \text{...})$&nbsp; a new event&nbsp; $E_ν$.&nbsp; Here,&nbsp; let hold:
 
[[File:En_Sto_T_1_4_S1.png |right|frame|Possible events and event sequence]]
 
[[File:En_Sto_T_1_4_S1.png |right|frame|Possible events and event sequence]]
 +
 
:$$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_M \}.$$
 
:$$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_M \}.$$
  
This mathematically not quite proper nomenclature means (see graph):
+
This mathematically not quite proper nomenclature means&nbsp; (see graph):
*The&nbsp; $M$&nbsp; possible events are numbered consecutively with the index&nbsp; $μ$&nbsp;.
+
*The&nbsp; $M$&nbsp; possible events are numbered consecutively with the index&nbsp; $μ$.
 +
 
 
*The index&nbsp; $ν$&nbsp; names the discrete time points at which events occur.
 
*The index&nbsp; $ν$&nbsp; names the discrete time points at which events occur.
  
  
For simplicity, we restrict ourselves in the following to the case&nbsp; $M = 2$&nbsp; with the universal set&nbsp; $G = \{ A, \ B \}$.&nbsp; Let further hold:
+
For simplicity,&nbsp; we restrict ourselves in the following to the case&nbsp; $M = 2$&nbsp; with the universal set&nbsp; $G = \{ A, \ B \}$.&nbsp; Let further hold:
*The probability of event&nbsp; $E_ν$&nbsp; may well depend on all previous events – that is, on events&nbsp; $E_{ν\hspace{0.05cm}-1},&nbsp; E_{ν\hspace{0.05cm}-2},&nbsp; E_{ν\hspace{0.05cm}-3},$&nbsp;, and so on.
+
*The probability of event&nbsp; $E_ν$&nbsp; may well depend on all previous events&nbsp; – that is,&nbsp; on the events&nbsp; $E_{ν\hspace{0.05cm}-1}, \hspace{0.15cm} E_{ν\hspace{0.05cm}-2}, \hspace{0.15cm} E_{ν\hspace{0.05cm}-3}$,&nbsp; and so on.&nbsp;
*This statement also means that in this chapter we consider a&nbsp; ''sequence of events with internal statistical ties''&nbsp;.  
+
 
 +
* This statement also means that in this chapter we consider a&nbsp; &raquo;sequence of events with internal statistical bindings&laquo;.  
  
  
This scenario is a special case of a discrete-time, discrete-value random process, which will be discussed in more detail in the chapter&nbsp;} [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Zufallsprozesse|Random Processes]]&nbsp; to be discussed in more detail.
+
This scenario is a special case of a discrete-time, discrete-value random process, which will be discussed in more detail in the chapter&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function#Random_processes|&raquo;Random Processes&laquo;]].&nbsp; 
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Example 1:}$&nbsp;
 
$\text{Example 1:}$&nbsp;
Cards are drawn one after the other from a deck of&nbsp; $32$&nbsp; cards (including four aces). With the events
+
Cards are drawn one after the other from a deck of&nbsp; $32$&nbsp; cards&nbsp; $($including four aces$)$.&nbsp; With the events
*$A\text{ :}=$&nbsp; „the drawn card is an ace”, and
+
*$A:=$&nbsp; &raquo;the drawn card is an ace&laquo;,&nbsp; 
*$B = \overline{A}:=$&nbsp; „the drawn card is not an ace”, the probabilities at time&nbsp; $ν = 1$:
+
*$B = \overline{A}:=$&nbsp; &raquo;the drawn card is not an ace&laquo;,&nbsp;
:$${\rm Pr} (A_{\rm 1})  ={4}/{32}= {1}/{8}, \hspace{0.5cm}{\rm Pr} (B_{\rm 1}) = {28}/{32}= {7}/{8}.$$
+
 
 +
 +
the probabilities at time&nbsp; $ν = 1$:
 +
:$${\rm Pr} (A_{\rm 1})  ={4}/{32}= {1}/{8},\hspace{0.5cm}{\rm Pr} (B_{\rm 1}) = {28}/{32}= {7}/{8}.$$
  
 
The probability&nbsp; ${\rm Pr} (A_{\rm 2})$,&nbsp; that an ace is drawn as the second card&nbsp; $(ν = 2)$&nbsp; now depends on,
 
The probability&nbsp; ${\rm Pr} (A_{\rm 2})$,&nbsp; that an ace is drawn as the second card&nbsp; $(ν = 2)$&nbsp; now depends on,
*whether an ace was drawn at time&nbsp; $ν = 1$&nbsp;&nbsp;  ⇒ &nbsp; ${\rm Pr} (A_{\rm 2})  = 3/31 < 1/8$,&nbsp;    or
+
*whether an ace was drawn at time&nbsp; $ν = 1$&nbsp;&nbsp;  ⇒ &nbsp; ${\rm Pr} (A_{\rm 2})  = 3/31 < 1/8$,&nbsp;
*whether at time&nbsp; $ν = 1$&nbsp; no ace was drawn &nbsp; ⇒ &nbsp; ${\rm Pr} (A_{\rm 2})  = 4/31 > 1/8$.  
+
    
 +
*or at time&nbsp; $ν = 1$&nbsp; no ace was drawn &nbsp; ⇒ &nbsp; ${\rm Pr} (A_{\rm 2})  = 4/31 > 1/8$.  
  
  
Also, the probabilities&nbsp; ${\rm Pr} (A_{\nu})$&nbsp; at later times&nbsp; $ν$&nbsp; always depend on the occurrence or non-occurrence of all previous events&nbsp; $E_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} ,E_{ν\hspace{0.05cm}–1}$&nbsp;.}}
+
Also,&nbsp; the probabilities&nbsp; ${\rm Pr} (A_{\nu})$&nbsp; at later times&nbsp; $ν$&nbsp; always depend on the occurrence or non-occurrence of all previous events&nbsp; $E_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} ,E_{ν\hspace{0.05cm}–1}$&nbsp;.}}
  
 
==General definition of a Markov chain==
 
==General definition of a Markov chain==
 
<br>
 
<br>
In special cases, which however occur very frequently, the scenario described above can be described by a Markov chain.
+
In special cases,&nbsp; which however occur very frequently,&nbsp; the scenario described above can be described by a Markov chain.
 
 
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Definition:}$&nbsp;
 
$\text{Definition:}$&nbsp;
A&nbsp; $k$-th order'''Markov Chain'''&nbsp; serves as a model for time- and value-discrete processes, where
+
A&nbsp; $k$-th order&nbsp; &raquo;'''Markov Chain'''&laquo;&nbsp; serves as a model for time and value-discrete processes,&nbsp; where the event probabilities at time&nbsp; $ν$  
#&nbsp;the event probabilities at time&nbsp; $ν$&nbsp; depend on the previous events &nbsp; $E_{ν\hspace{0.05cm}–1}, \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_{ν\hspace{0.05cm}–k}$&nbsp; abhängen, and  
+
*&nbsp;&nbsp; depend on the previous events &nbsp; $E_{ν\hspace{0.05cm}–1}, \hspace{0.15cm}\text{...}\hspace{0.15cm}, E_{ν\hspace{0.05cm}–k}$,&nbsp; and
#&nbsp; can be expressed by&nbsp; $M^{k+1}$&nbsp; conditional probabilities.}}  
+
 +
*&nbsp; can be expressed by&nbsp; $M^{k+1}$&nbsp; conditional probabilities.}}  
  
  
[[File:EN_Sto_T_1_4_S2a.png |right|frame| Second order Markov chain]]
+
[[File:EN_Sto_T_1_4_S2a.png |right|frame| Second order Markov chain]]  
 +
The diagram illustrates this issue using&nbsp; $k = 2$&nbsp; as an example.&nbsp;
  
The diagram illustrates this issue using&nbsp; $k = 2$ as an example..
+
*For&nbsp; $M = 2$&nbsp; there are&nbsp; $2^{k+1}$&nbsp; such conditional probabilities:&nbsp;
  
Therefore, for&nbsp; $M = 2$&nbsp; there are&nbsp; $2^{k+1}$&nbsp; such conditional probabilities.&nbsp;
+
:$${\rm Pr} ( E_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}E_{\nu {\rm -1 } },\hspace {0.15cm}\text{...}\hspace {0.15cm}, E_{\nu { -k } }).$$
:$${\rm Pr} ( E_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}E_{\nu {\rm -1 } },\hspace {0.1cm}\text{...}\hspace {0.1cm}, E_{\nu { -k } }).$$
 
 
 
With&nbsp; $E_{\nu }\in \{ A, B \}, \hspace {0.1cm}\text{...}\hspace {0.1cm}, E_{\nu { -k } } \in \{ A, B \}$&nbsp; these are:
 
*${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } })$, &nbsp;${\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } })$, &nbsp;
 
*${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } },B_{\nu { -2 } })$, &nbsp;${\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, B_{\nu { -2 } })$, &nbsp;
 
*${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } })$, &nbsp;${\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } })$, &nbsp;
 
*${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } })$, &nbsp;${\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } })$.
 
  
 +
*With&nbsp; $E_{\nu }\in \{ A, B \}, \hspace {0.15cm}\text{...}\hspace {0.15cm}, E_{\nu { -k } } \in \{ A, B \}$&nbsp; these are:
 +
:$${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } }),\hspace {0.5cm} {\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } }),$$
 +
:$${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } },B_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}A_{\nu {\rm -1 } }, B_{\nu { -2 } }),$$
 +
:$${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } }),$$
 +
:$${\rm Pr} ( A_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu  \hspace {0.05cm}\vert  \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } }).$$
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Example 2:}$&nbsp; Natural languages are often describable by Markov chains, although the order&nbsp; $k$&nbsp; tends to infinity.&nbsp; In this example, however, texts are only approximated by second-order Markov chains.
+
$\text{Example 2:}$&nbsp; Natural languages are often describable by Markov chains,&nbsp; although the order&nbsp; $k$&nbsp; tends here to infinity.&nbsp;  
 
 
[[File:EN_Sto_T_1_4_S2c.png |center|frame| Synthetically generated texts (German and English)]]
 
  
 +
In this example,&nbsp; however,&nbsp; texts are only approximated by second order Markov chains.
 +
[[File:EN_Sto_T_1_4_S2c.png |right|frame| Synthetically generated texts&nbsp; based on German or English book template]]
 
The graphic shows two synthetically generated texts:
 
The graphic shows two synthetically generated texts:
 
*The left text was synthetically generated starting from a German book template with bindings up to second order.
 
*The left text was synthetically generated starting from a German book template with bindings up to second order.
*For the right text, an English template was used.
 
  
 +
*For the right text,&nbsp; an English book template was used.
 +
 +
 +
One recognizes despite the restriction to&nbsp; $k = 2$&nbsp; 
 +
#many $($short$)$ German words on the left,
 +
#many $($short$)$ English words on the right,
 +
#German words are on the average longer than English words.&nbsp;
  
One recognizes despite the restriction to&nbsp; $k = 2$&nbsp;  many (short) German and/or English words and also that German words are on the average longer than English.&nbsp; There is no meaningful content, but the structure of the respective language is recognizable. }}
 
  
==Markovkette erster Ordnung==
+
There is no meaningful content,&nbsp; but the structure of the respective language is recognizable. }}
 +
 
 +
==First order Markov chain==
 
<br>
 
<br>
Im Folgenden beschränken wir uns stets auf den Sonderfall&nbsp; $k =1$ .
+
In the following, we always restrict ourselves to the special case&nbsp; $k =1$.
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Bei einer&nbsp; '''Markovkette erster Ordnung'''&nbsp; (englisch:&nbsp; ''First Order Markov Chain'')&nbsp; wird lediglich die statistische Bindung zum letzten Ereignis berücksichtigt, die in der Praxis meist auch am stärksten ist.  
+
$\text{Definition:}$&nbsp;  
 +
 
 +
$(1)$&nbsp; In a&nbsp; &raquo;'''first order Markov chain'''&laquo;&nbsp; only the statistical binding to the last event is considered,&nbsp; which in practice is usually the strongest.
  
Eine binäre Markovkette erster Ordnung &nbsp;  ⇒  &nbsp; Grundmenge&nbsp; $G = \{ A, \ B \}$&nbsp; weist zum Zeitpunkt&nbsp; $\nu$&nbsp; folgende Ereigniswahrscheinlichkeiten auf:
+
$(2)$&nbsp; For example:&nbsp; A&nbsp; &raquo;'''binary first order Markov chain'''&laquo;&nbsp;  ⇒  &nbsp; universal set&nbsp; $G = \{ A, \ B \}$&nbsp; has the following event probabilities at time&nbsp; $\nu$:
 
:$${\rm Pr}(A_\nu) = {\rm Pr}(A_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) ,$$
 
:$${\rm Pr}(A_\nu) = {\rm Pr}(A_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) ,$$
 
:$${\rm Pr}(B_\nu) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) .$$}}
 
:$${\rm Pr}(B_\nu) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) .$$}}
  
  
Zu diesen Gleichungen ist anzumerken:  
+
Regarding these equations,&nbsp; we note:  
*${\rm Pr}(A_\nu)$&nbsp; steht als Abkürzung für die Wahrscheinlichkeit, dass zur Zeit&nbsp; $ν$&nbsp; das Ereignis&nbsp; $E_ν = A = \overline{B}$&nbsp; auftritt, und es gilt&nbsp;   ${\rm Pr}(B_\nu) = 1 - {\rm Pr}(A_\nu)$
+
*${\rm Pr}(A_\nu)$&nbsp; is shorthand for the probability that at time&nbsp; $ν$&nbsp; the event &nbsp; $E_ν = A = \overline{B}$&nbsp; occurs,&nbsp; and it    holds:
*Zu jedem Zeitpunkt gibt es vier Übergangswahrscheinlichkeiten&nbsp; ${\rm Pr}(E_ν\hspace{0.05cm} |\hspace{0.05cm} E_{ν–1})$, von denen jedoch nur zwei unabhängig sind, denn es gilt:
+
:$${\rm Pr}(B_\nu) = 1 - {\rm Pr}(A_\nu).$$
:$${\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}).$$
+
*At each time there are four transition probabilities&nbsp; ${\rm Pr}(E_ν\hspace{0.05cm} |\hspace{0.05cm} E_{ν–1})$,&nbsp; but only two of them are independent,&nbsp; because it holds:
*Durch Verallgemeinerung dieser letzten Aussage gelangt man zu dem Ergebnis, dass es bei einer Markovkette mit&nbsp; $M$ Ereignissen&nbsp; zu jedem Zeitpunkt&nbsp; $ν$&nbsp; genau&nbsp; $M · (M – 1)$&nbsp; voneinander unabhängige Übergangswahrscheinlichkeiten gibt.
+
:$${\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}),$$
 +
:$${\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}).$$
 +
*Generalizing this last statement:&nbsp; For a Markov chain with&nbsp; $M$ events,&nbsp; there are exactly&nbsp; $M · (M – 1)$&nbsp; independent transition probabilities at each time&nbsp; $ν$.
  
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 3:}$&nbsp; Mit den vorgegebenen Übergangswahrscheinlichkeiten
+
$\text{Example 3:}$&nbsp; With the given transition probabilities
:$${\rm Pr}(A_ν\hspace{0.05cm}\vert\hspace{0.05cm} A_{ν–1}) = 0.2 \hspace{0.3cm}\text{und}\hspace{0.3cm}  {\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 0.4$$  
+
:$${\rm Pr}(A_ν\hspace{0.05cm}\vert\hspace{0.05cm} A_{ν–1}) = 0.2, \hspace{0.5cm}  {\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 0.4,$$  
sind auch die beiden anderen Übergangswahrscheinlichkeiten eindeutig festgelegt:  
+
the other two transition probabilities are also uniquely specified:
:$${\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} A_{ν–1}) = 1- 0.2 = 0.8 \hspace{0.3cm}\text{und}\hspace{0.3cm}
+
:$${\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} A_{ν–1}) = 1- 0.2 = 0.8, \hspace{0.5cm}
 
{\rm Pr}(A_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 1- 0.4 = 0.6.$$}}
 
{\rm Pr}(A_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 1- 0.4 = 0.6.$$}}
  
==Homogene Markovketten==
+
==Homogeneous Markov chains==
 
<br>
 
<br>
Eine Anwendbarkeit der Markovketten auf praktische Probleme ist meist nur bei weiteren einschränkenden Voraussetzungen gegeben.
+
Applicability of Markov chains to practical problems is usually only given with further restrictive conditions.
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Sind alle Übergangswahrscheinlichkeiten unabhängig vom betrachteten Zeitpunkt&nbsp; $ν$, so ist die Markovkette&nbsp; '''homogen'''&nbsp; (englisch:&nbsp; ''homogeneous'').  
+
$\text{Definition:}$&nbsp;
 +
 +
$(1)$&nbsp; If all transition probabilities are independent of time&nbsp; $ν$,&nbsp; the Markov chain is&nbsp; &raquo;'''homogeneous'''&laquo;.
  
Im Fall&nbsp; $M = 2$&nbsp; verwenden wir hierfür folgende Abkürzungen:
+
$(2)$&nbsp; In the case&nbsp; $M = 2$&nbsp; we use the following abbreviations:
 
:$${\rm Pr}(A \hspace{0.05cm} \vert \hspace{0.05cm}A) = {\rm Pr}(A_\nu \hspace{0.05cm}\vert \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(A \hspace{0.05cm} \vert\hspace{0.05cm}B) = {\rm Pr}(A_\nu \hspace{0.05cm} \vert \hspace{0.05cm}B_{\nu - 1}) ,$$
 
:$${\rm Pr}(A \hspace{0.05cm} \vert \hspace{0.05cm}A) = {\rm Pr}(A_\nu \hspace{0.05cm}\vert \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(A \hspace{0.05cm} \vert\hspace{0.05cm}B) = {\rm Pr}(A_\nu \hspace{0.05cm} \vert \hspace{0.05cm}B_{\nu - 1}) ,$$
 
:$${\rm Pr}(B \hspace{0.05cm} \vert\hspace{0.05cm}A) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(B \hspace{0.05cm} \vert \hspace{0.05cm}B) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \hspace{0.05cm}B_{\nu - 1}) .$$}}
 
:$${\rm Pr}(B \hspace{0.05cm} \vert\hspace{0.05cm}A) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \hspace{0.05cm}A_{\nu - 1}) , \hspace{0.5cm} {\rm Pr}(B \hspace{0.05cm} \vert \hspace{0.05cm}B) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \hspace{0.05cm}B_{\nu - 1}) .$$}}
  
  
Damit lauten die Ereigniswahrscheinlichkeiten einer binären homogenen Markovkette, die absolute Wahrscheinlichkeiten darstellen im Gegensatz zu den bedingten Übergangswahrscheinlichkeiten :
+
[[File:P_ID1444__Sto_T_1_4_S4_neu.png|right|frame| First order homogeneous Markov chain]]
[[File:P_ID1444__Sto_T_1_4_S4_neu.png|right|frame| Homogene Markovkette erster Ordnung]]
+
Thus,&nbsp; the event probabilities of a binary homogeneous Markov chain:
 
:$${\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}(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}) .$$
 
:$${\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}) .$$
  
Auch aus dem Markovdiagramm kann man ablesen:
+
These are absolute probabilities in contrast to the conditional transition probabilities.
*Die Summe der&nbsp; '''abgehenden Pfeile'''&nbsp; eines Ereignisses ist stets Eins:
+
 
 +
We can also read from the Markov diagram:
 +
*The sum of the&nbsp; &raquo;'''outgoing arrows'''&laquo;&nbsp; of an event is always one:
 
:$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) =1,$$
 
:$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) =1,$$
 
:$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) =1.$$
 
:$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) =1.$$
  
*Die Summen&nbsp; ${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B)$&nbsp; bzw.&nbsp; ${\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B)$&nbsp;  unterliegen  dagegen keinen Einschränkungen.
+
*For the sums of the&nbsp; &raquo;'''incoming arrows'''&laquo;&nbsp; this restriction does not apply:
 +
:$$ 0 < {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B)< 2,$$
 +
:$$0 < {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B)< 2.$$
  
 +
==Stationary probabilities==
 +
<br>
 +
Important properties of random processes are&nbsp;  [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Stationary_random_processes|&raquo;$\text{stationarity}$&laquo;]]&nbsp;  and&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Ergodic_random_processes|&raquo;$\text{ergodicity}$&laquo;]].&nbsp; Although these terms are not defined until the fourth main chapter&nbsp; &raquo;Random Variables with Statistical Dependence&laquo;,&nbsp; we apply them here already in advance to Markov chains.
  
Sie können das „Einschwingverhalten” der Ereigniswahrscheinlichkeiten einer solchen binären Markovkette mit dem interaktiven Applet&nbsp; [[Applets:Markovketten|Ereigniswahrscheinlichkeiten einer Markovkette erster Ordnung]]&nbsp; berechnen und anzeigen lassen.
+
{{BlaueBox|TEXT=  
 +
$\text{Definition:}$&nbsp;  
 
   
 
   
==Stationäre Wahrscheinlichkeiten==
+
$(1)$&nbsp; If,&nbsp; in addition to the transition probabilities,&nbsp; all event probabilities of a Markov chain are independent of time&nbsp; $ν$,&nbsp; then the Markov chain is called&nbsp; &raquo;'''stationary'''&laquo;.&nbsp;
<br>
 
Wichtige Eigenschaften von Zufallsprozessen sind&nbsp; [[Theory_of_Stochastic_Signals/Autokorrelationsfunktion_(AKF)#Station.C3.A4re_Zufallsprozesse|Stationarität]]&nbsp; und&nbsp; [[Theory_of_Stochastic_Signals/Autokorrelationsfunktion_(AKF)#Ergodische_Zufallsprozesse|Ergodizität]].&nbsp; Obwohl diese Begriffe erst im vierten Hauptkapitel&nbsp; "Zufallsgrößen mit statistischen Bindungen"&nbsp; definiert werden, wenden wir sie hier bereits vorausgreifend auf Markovketten an.
 
  
{{BlaueBox|TEXT= 
+
$(2)$&nbsp; One then omits the index&nbsp; $ν$&nbsp; and writes in the binary case:
$\text{Definition:}$&nbsp; Sind bei einer Markovkette neben den Übergangswahrscheinlichkeiten auch alle Ereigniswahrscheinlichkeiten unabhängig von der Zeit&nbsp; $ν$, so bezeichnet man die Markovkette als&nbsp; '''stationär'''&nbsp; (englisch:&nbsp; ''stationary'').&nbsp; Man verzichtet dann auf den Index $ν$ und schreibt im binären Fall:
+
:$${\rm Pr}(A_\nu ) = {\rm Pr}(A ), \hspace{0.5 cm} {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$
:$${\rm Pr}(A_\nu ) = {\rm Pr}(A )  \hspace{0.5 cm} {\rm bzw.} \hspace{0.5 cm} {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$
+
$(3)$&nbsp; These quantities are also called&nbsp; &raquo;'''ergodic probabilities'''&laquo;&nbsp; of the Markov chain.}}
Diese Größen nennt man auch die&nbsp; '''ergodischen Wahrscheinlichkeiten'''&nbsp; der Markovkette.}}
 
  
  
Stationäre Markovketten weisen die nachfolgend genannten Besonderheiten auf:  
+
Stationary Markov chains have the special features mentioned below:
*Zur Berechnung der ergodischen Wahrscheinlichkeiten einer binären Markovkette&nbsp; $(M =2)$&nbsp; kann man folgende Gleichungen verwenden:
+
*To calculate the ergodic probabilities of a binary Markov chain&nbsp; $(M =2)$&nbsp; one can use the following equations:
 
:$${\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}(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) .$$
 
:$${\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 hiervon benutzen.&nbsp; Als zweite Bestimmungsgleichung kann man beispielsweise verwenden:  
+
*Since these equations depend linearly on each other,&nbsp; one may use only one of them.&nbsp;  As the second equation of determination one may use:
 
:$${\rm Pr}(A) +  {\rm Pr}(B)  = 1.$$
 
:$${\rm Pr}(A) +  {\rm Pr}(B)  = 1.$$
  
*Die ergodischen Wahrscheinlichkeiten ergeben sich daraus zu
+
*The ergodic probabilities result from it to
:$${\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) }.$$
+
:$${\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}, $$
 +
:$${\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) }.$$
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 4:}$&nbsp; Wir betrachten eine binäre Markovkette mit den Ereignissen&nbsp; $A$&nbsp; und $B$&nbsp; und den Übergangswahrscheinlichkeiten&nbsp; ${\rm Pr}(A \hspace{0.05cm} \vert\hspace{0.05cm}A) = 0.4$&nbsp; und&nbsp;  ${\rm Pr}(B \hspace{0.05cm} \vert \hspace{0.05cm}B) = 0.8$. <br>Weiterhin setzen wir voraus, dass jede Realisierung dieser Kette zum Startzeitpunkt&nbsp; $ν = 0$&nbsp; mit dem Ereignis&nbsp; $A$&nbsp; beginnt.
+
$\text{Example 4:}$&nbsp; We consider a stationary and binary Markov chain with events&nbsp; $A$&nbsp; and $B$&nbsp; and transition probabilities&nbsp; ${\rm Pr}(A \hspace{0.05cm} \vert\hspace{0.05cm}A) = 0.4$&nbsp; and&nbsp;  ${\rm Pr}(B \hspace{0.05cm} \vert \hspace{0.05cm}B) = 0.8$.
 
+
[[File:P_ID642__Sto_T_1_4_S5_neu.png |right|frame| Transient response of the event probabilities $($three decimal places$)$]]
Man erhält dann die nachfolgend aufgelisteten Ereigniswahrscheinlichkeiten (mit drei Nachkommastellen):  
+
 
+
Furthermore,&nbsp; we assume that each realization starts with event&nbsp; $A$&nbsp; at starting time&nbsp; $ν = 0$.&nbsp; We then obtain the event probabilities listed on the right:  
[[File:P_ID642__Sto_T_1_4_S5_neu.png |center|frame| Zum Einschwingen der Ereigniswahrscheinlichkeiten]]
 
  
Es handelt sich hier im strengen Sinne um eine nichtstationäre Markovkette, die jedoch schon nach kurzer Zeit (nahezu) eingeschwungen ist:  
+
In a strict sense,&nbsp; this is a non-stationary Markov chain,&nbsp; but it is&nbsp; $($nearly$)$&nbsp; settled after a short time:
*Zu späteren Zeiten&nbsp; $(ν > 5)$&nbsp; werden die Ereigniswahrscheinlichkeiten&nbsp; ${\rm Pr}(A_ν) \approx 1/4$&nbsp; und&nbsp; ${\rm Pr}(B_ν) \approx 3/4$&nbsp; nicht mehr gravierend verändert.  
+
#At later times&nbsp; $(ν > 5),$&nbsp; the event probabilities&nbsp; ${\rm Pr}(A_ν) \approx 1/4$,&nbsp; ${\rm Pr}(B_ν) \approx 3/4$&nbsp; are no longer seriously changed.
*Aus der Angabe&nbsp; ${\rm Pr}(A_{ν=5}) = 0.250$&nbsp; und&nbsp;  ${\rm Pr}(B_{ν=5}) = 0.750$&nbsp; sollte allerdings  nicht geschlossen werden, dass die Markovkette zum Zeitpunkt&nbsp; $ν = 5$&nbsp; schon vollkommen eingeschwungen ist.
+
#However,&nbsp; from&nbsp; ${\rm Pr}(A_{ν=5}) = 0.250$&nbsp; and&nbsp;  ${\rm Pr}(B_{ν=5}) = 0.750$&nbsp; it should not be concluded that the Markov chain is already perfectly steady at time &nbsp; $ν = 5$.
*Die exakten Werte sind nämlich&nbsp; ${\rm Pr}(A_{ν=5}) = 0.25024$&nbsp; und&nbsp; ${\rm Pr}(B_{ν=5}) = 0.74976$.}}
+
#Indeed,&nbsp; the exact values are:&nbsp;  
 +
::$${\rm Pr}(A_{ν=5}) = 0.25024,\hspace{0.5cm}{\rm Pr}(B_{ν=5}) = 0.74976.$$}}
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Fazit:}$&nbsp; Bei einer stationären Markovkette treten sehr lange nach Einschalten der Kette&nbsp; $(ν → ∞)$&nbsp; mit guter Näherung stets die ergodischen Wahrscheinlichkeiten auf, unabhängig von den Startbedingungen&nbsp; ${\rm Pr}(A_0)$&nbsp; und&nbsp; ${\rm Pr}(B_0) = 1 - {\rm Pr}(A_0)$.
+
$\text{Conclusion:}$&nbsp; For a stationary Markov chain, the ergodic probabilities always occur with good approximation very long after the chain is switched on &nbsp; $(ν → ∞)$&nbsp;, regardless of the initial conditions&nbsp; ${\rm Pr}(A_0)$&nbsp; and&nbsp; ${\rm Pr}(B_0) = 1 - {\rm Pr}(A_0)$.
 
}}
 
}}
  
==Matrix-Vektordarstellung==
+
==Matrix vector representation==
 
<br>
 
<br>
Homogene Markovketten können mit Vektoren und Matrizen sehr kompakt dargestellt werden. Dies empfiehlt sich insbesondere bei mehr als zwei Ereignissen:
+
Homogeneous Markov chains can be represented very compactly with vectors and matrices.&nbsp; This is especially recommended for more than two events:
:$$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_M \}.$$
 
Für die Matrix-Vektorendarstellung verwenden wir folgende Nomenklatur:
 
*Die&nbsp; $M$&nbsp; Wahrscheinlichkeiten zum Zeitpunkt&nbsp; $ν$&nbsp; fassen wir in einem Spaltenvektor zusammen:
 
:$${\mathbf{p}^{(\nu)}} = \left[ \begin{array}{c} {p_{\rm 1}}^{(\nu)} \\ \dots \\ {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&nbsp; $M \times 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} \\ \dots & \dots & \dots & \dots \\ 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).$$
 
  
 +
:$$E_\nu \in G = \{ E_{\rm 1},\ E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm},\ E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm},\ E_M \}.$$
 +
For the matrix-vector representation,&nbsp; we use the following nomenclature:
 +
*We summarize the&nbsp; $M$&nbsp; probabilities at time&nbsp; $ν$&nbsp; in a column vector:
 +
:$${\mathbf{p}^{(\nu)}} = \left[ \begin{array}{c} {p_{\rm 1}}^{(\nu)} \\ \dots \\ {p_{M}}^{(\nu)} \end{array} \right] \hspace{0.5cm}{\rm with} \hspace{0.5cm} {p_{\mu}}^{(\nu)} = {\rm Pr}(E_\nu = E_\mu ).$$
 +
*The transition probabilities are expressed by an&nbsp; $M \times M$ matrix:
 +
:$${\mathbf{P}} =\left( p_{ij} \right) = \left[ \begin{array}{cccc} p_{11} & p_{12} & \cdots & p_{1M} \\ p_{21} & p_{22}& \cdots & p_{2M} \\ \dots & \dots & \dots & \dots \\ p_{M1} & p_{M2} & \cdots & p_{MM}  \end{array} \right] \hspace{0.5cm}{\rm with} \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&nbsp; $M = 2$.&nbsp; Der neue Ereigniswahrscheinlichkeitsvektor nach einem Schritt lautet:  
+
The accompanying figure illustrates this nomenclature using the example&nbsp; $M = 2$.&nbsp; The new event probability vector after one step is:
[[File:P_ID448__Sto_T_1_4_S6_neu.png  |frame|Zur Bezeichnung der Übergangswahrscheinlichkeiten |right]]
+
[[File:P_ID448__Sto_T_1_4_S6_neu.png  |frame|To denote the transition probabilities |right]]
 
:$${\mathbf{p}^{(\nu + 1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(\nu )}} .$$
 
:$${\mathbf{p}^{(\nu + 1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(\nu )}} .$$
  
${\mathbf{P}^{\rm T}}$&nbsp; bezeichnet hierbei die&nbsp; ''transponierte''&nbsp; Matrix zu&nbsp; $\mathbf{P}$.&nbsp; Nach&nbsp; $n$&nbsp; Schritten ergibt sich somit
+
Here,&nbsp; ${\mathbf{P}^{\rm T}}$&nbsp; denotes the&nbsp; &raquo;transposed matrix&raquo;&nbsp; to&nbsp; $\mathbf{P}$.&nbsp; Thus,&nbsp; after&nbsp; $n$&nbsp; steps,&nbsp; the result is
 
:$${\mathbf{p}^{(\nu +{\it n})}} = \left( {\mathbf{P}}^{\rm T} \right)^n \cdot {\mathbf{p}^{(\nu )}} .$$
 
:$${\mathbf{p}^{(\nu +{\it n})}} = \left( {\mathbf{P}}^{\rm T} \right)^n \cdot {\mathbf{p}^{(\nu )}} .$$
  
Im Grenzübergang&nbsp; $(n → ∞)$&nbsp; erreicht man dann stets die Stationarität der Markovkette:
+
In the limit transition&nbsp; $(n → ∞)$&nbsp; one then always achieves stationarity of the Markov chain:
 
:$$\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}} \\ \dots \\ {p_{M}} \end{array} \right] .$$
 
:$$\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}} \\ \dots \\ {p_{M}} \end{array} \right] .$$
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Multipliziert man die Übergangsmatrix&nbsp; ${\mathbf{P} }$&nbsp; unendlich oft mit sich selbst und benennt das Ergebnis mit&nbsp; ${\mathbf{P} }_{\rm erg}$, so besteht die resultierende Matrix aus&nbsp; $M$&nbsp; gleichen Zeilen:
+
$\text{Definition:}$&nbsp; Multiplying the transition matrix&nbsp; ${\mathbf{P} }$&nbsp; infinitely many times by itself and denoting the result by&nbsp; ${\mathbf{P} }_{\rm erg}$,&nbsp; the resulting matrix consists of&nbsp; $M$&nbsp; equal rows:
 
:$${\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} \\ \dots & \dots & \dots & \dots \\ p_{1} & p_{2} & \cdots & p_{M}  \end{array} \right] .$$
 
:$${\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} \\ \dots & \dots & \dots & \dots \\ p_{1} & p_{2} & \cdots & p_{M}  \end{array} \right] .$$
Die Wahrscheinlichkeiten&nbsp; $p_1, \hspace{0.1cm}\text{...}\hspace{0.1cm}, p_M$&nbsp; in jeder dieser Zeilen bezeichnet man als die&nbsp; '''ergodischen Wahrscheinlichkeiten'''. }}
+
The probabilities&nbsp; $p_1, \hspace{0.15cm}\text{...}\hspace{0.15cm}, p_M$&nbsp; in each of these lines are called the&nbsp; &raquo;'''ergodic probabilities'''&laquo;. }}
 +
 
  
  
[[File:P_ID1445__Sto_T_1_4_S6c_neu.png | right|frame|Markovdiagramm mit drei Ereignissen]]
 
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 5:}$&nbsp; Wir betrachten beispelhaft eine Markovkette mit den Ereignissen&nbsp; $E_1,&nbsp; E_2$&nbsp; und&nbsp; $E_3$ &nbsp; &rArr; &nbsp; $M=3$. Die Grafik zeigt
+
$\text{Example 5:}$&nbsp; We consider a Markov chain with the events&nbsp; $E_1,&nbsp; E_2$&nbsp; and&nbsp; $E_3$ &nbsp; &rArr; &nbsp; $M=3$.&nbsp; The graph shows
*links das Markovdiagramm,  
+
[[File:P_ID1445__Sto_T_1_4_S6c_neu.png | right|frame|Markov diagram with three events]]
*rechts oben die Übergangsmatrix&nbsp; $\mathbf{P}$ und
+
*on the left the Markov diagram,
*darunter deren Potenzen&nbsp; $\mathbf{P}^2$&nbsp; und&nbsp; $\mathbf{P}^3$.  
+
*on the upper right the transition matrix&nbsp; $\mathbf{P}$,
 +
*below their powers&nbsp; $\mathbf{P}^2$&nbsp; and&nbsp; $\mathbf{P}^3$.  
  
  
Im Markovdiagramm sind alle Übergangswahrscheinlichkeiten mit dem Zahlenwert&nbsp; $1/2$&nbsp; blau eingezeichnet;&nbsp; grün kennzeichnet die Wahrscheinlichkeit&nbsp; $1/4$.
+
In the Markov diagram,&nbsp; all transition probabilities with the numerical value&nbsp; $1/2$&nbsp; are shown in blue; &nbsp; green indicates the probability&nbsp; $1/4$.
*Beim Start&nbsp; $(ν =0)$&nbsp; seien alle Ereignisse gleichwahrscheinlich.&nbsp; Für&nbsp; $ν = 1$&nbsp; gilt dann:
+
*At the start&nbsp; $(ν =0)$&nbsp; all events are equally probable.&nbsp; For&nbsp; $ν = 1$&nbsp; then holds:
 
:$${\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] .$$
 
:$${\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&nbsp;  $\mathbf{P}$&nbsp; durch den Austausch der Zeilen und Spalten zur transponierten Matrix&nbsp; ${\mathbf{P}^{\rm T} }$&nbsp; kommt.  
+
:From this it can be seen that we get from the matrix&nbsp;  $\mathbf{P}$&nbsp; to the transposed matrix&nbsp; ${\mathbf{P}^{\rm T} }$&nbsp; by exchanging rows and columns.  
*Zum Zeitpunkt&nbsp; $ν =2$&nbsp; (und auch zu allen späteren Zeiten) ergeben sich die gleichen Wahrscheinlichkeiten:
+
 
 +
*At time&nbsp; $ν =2$&nbsp; $($and also at all later times$)$&nbsp; the same probabilities result:
 
:$${\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] .$$
 
:$${\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:&nbsp; Die ergodischen Wahrscheinlichkeiten der drei Ereignisse sind&nbsp;  $1/2$&nbsp; $($für&nbsp; $E_1)$,&nbsp; $1/4$&nbsp; $($für&nbsp; $E_2)$,&nbsp; und $1/4$&nbsp; $($für&nbsp; $E_3)$.  
+
:This means:&nbsp; The ergodic probabilities of the three events are&nbsp;  $1/2$&nbsp; $($for&nbsp; $E_1)$,&nbsp; $1/4$&nbsp; $($for&nbsp; $E_2)$,&nbsp; and $1/4$&nbsp; $($for&nbsp; $E_3)$.  
*Dieses Ergebnis hätte man auch direkt aus der ergodischen Matrix ablesen können:
+
*This result could have been read directly from the ergodic matrix:
 
:$${\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] .$$
 
:$${\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.  
+
:This is obtained by continuously multiplying the transition matrix by itself.
*Im obigen Bild sind die Potenzen&nbsp;  $\mathbf{P}^2$&nbsp; und&nbsp; $\mathbf{P}^3$&nbsp; angegeben, die sich der Matrix&nbsp; $\mathbf{P}_{\rm erg}$&nbsp; annähern.}}
+
*In the figure above the powers&nbsp;  $\mathbf{P}^2$&nbsp; and&nbsp; $\mathbf{P}^3$&nbsp; are given,&nbsp; which approximate the matrix&nbsp; $\mathbf{P}_{\rm erg}$.}}
  
==Aufgaben zum Kapitel==
+
==Exercises for the chapter==
  
[[Aufgaben:1.6_Übergangswahrscheinlichkeiten|Aufgabe 1.6: Übergangswahrscheinlichkeiten]]
+
[[Aufgaben:Exercise_1.6:_Transition_Probabilities|Exercise 1.6: Transition Probabilities]]
  
[[Aufgaben:1.6Z_Ergodische_Wahrscheinlichkeiten|Aufgabe 1.6Z: Ergodische Wahrscheinlichkeiten]]
+
[[Aufgaben:Exercise_1.6Z:_Ergodic_Probabilities|Exercise 1.6Z: Ergodic Probabilities]]
  
[[Aufgaben:1.7 Ternäre Markovkette|Aufgabe 1.7: Ternäre Markovkette]]
+
[[Aufgaben:Exercise_1.7:_Ternary_Markov_Chain|Exercise 1.7: Ternary Markov Chain]]
  
[[Aufgaben:1.7Z_BARBARA-Generator|Aufgabe 1.7Z: BARBARA-Generator]]
+
[[Aufgaben:Exercise_1.7Z:_BARBARA_Generator|Exercise 1.7Z: BARBARA Generator]]
  
  
 
{{Display}}
 
{{Display}}

Latest revision as of 13:51, 6 February 2024

Considered scenario


Finally,  we consider the case where one conducts a random experiment continuously and that at each discrete time  $(ν = 1, 2, 3, \text{...})$  a new event  $E_ν$.  Here,  let hold:

Possible events and event sequence
$$E_\nu \in G = \{ E_{\rm 1}, E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm}, E_M \}.$$

This mathematically not quite proper nomenclature means  (see graph):

  • The  $M$  possible events are numbered consecutively with the index  $μ$.
  • The index  $ν$  names the discrete time points at which events occur.


For simplicity,  we restrict ourselves in the following to the case  $M = 2$  with the universal set  $G = \{ A, \ B \}$.  Let further hold:

  • The probability of event  $E_ν$  may well depend on all previous events  – that is,  on the events  $E_{ν\hspace{0.05cm}-1}, \hspace{0.15cm} E_{ν\hspace{0.05cm}-2}, \hspace{0.15cm} E_{ν\hspace{0.05cm}-3}$,  and so on. 
  • This statement also means that in this chapter we consider a  »sequence of events with internal statistical bindings«.


This scenario is a special case of a discrete-time, discrete-value random process, which will be discussed in more detail in the chapter  »Random Processes«.  

$\text{Example 1:}$  Cards are drawn one after the other from a deck of  $32$  cards  $($including four aces$)$.  With the events

  • $A:=$  »the drawn card is an ace«, 
  • $B = \overline{A}:=$  »the drawn card is not an ace«, 


the probabilities at time  $ν = 1$:

$${\rm Pr} (A_{\rm 1}) ={4}/{32}= {1}/{8},\hspace{0.5cm}{\rm Pr} (B_{\rm 1}) = {28}/{32}= {7}/{8}.$$

The probability  ${\rm Pr} (A_{\rm 2})$,  that an ace is drawn as the second card  $(ν = 2)$  now depends on,

  • whether an ace was drawn at time  $ν = 1$   ⇒   ${\rm Pr} (A_{\rm 2}) = 3/31 < 1/8$, 
  • or at time  $ν = 1$  no ace was drawn   ⇒   ${\rm Pr} (A_{\rm 2}) = 4/31 > 1/8$.


Also,  the probabilities  ${\rm Pr} (A_{\nu})$  at later times  $ν$  always depend on the occurrence or non-occurrence of all previous events  $E_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} ,E_{ν\hspace{0.05cm}–1}$ .

General definition of a Markov chain


In special cases,  which however occur very frequently,  the scenario described above can be described by a Markov chain.

$\text{Definition:}$  A  $k$-th order  »Markov Chain«  serves as a model for time and value-discrete processes,  where the event probabilities at time  $ν$

  •    depend on the previous events   $E_{ν\hspace{0.05cm}–1}, \hspace{0.15cm}\text{...}\hspace{0.15cm}, E_{ν\hspace{0.05cm}–k}$,  and
  •   can be expressed by  $M^{k+1}$  conditional probabilities.


Second order Markov chain

The diagram illustrates this issue using  $k = 2$  as an example. 

  • For  $M = 2$  there are  $2^{k+1}$  such conditional probabilities: 
$${\rm Pr} ( E_\nu \hspace {0.05cm}\vert \hspace {0.05cm}E_{\nu {\rm -1 } },\hspace {0.15cm}\text{...}\hspace {0.15cm}, E_{\nu { -k } }).$$
  • With  $E_{\nu }\in \{ A, B \}, \hspace {0.15cm}\text{...}\hspace {0.15cm}, E_{\nu { -k } } \in \{ A, B \}$  these are:
$${\rm Pr} ( A_\nu \hspace {0.05cm}\vert \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } }),\hspace {0.5cm} {\rm Pr} ( B_\nu \hspace {0.05cm}\vert \hspace {0.05cm}A_{\nu {\rm -1 } }, A_{\nu { -2 } }),$$
$${\rm Pr} ( A_\nu \hspace {0.05cm}\vert \hspace {0.05cm}A_{\nu {\rm -1 } },B_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu \hspace {0.05cm}\vert \hspace {0.05cm}A_{\nu {\rm -1 } }, B_{\nu { -2 } }),$$
$${\rm Pr} ( A_\nu \hspace {0.05cm}\vert \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu \hspace {0.05cm}\vert \hspace {0.05cm}B_{\nu {\rm -1 } }, A_{\nu { -2 } }),$$
$${\rm Pr} ( A_\nu \hspace {0.05cm}\vert \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } }),\hspace {0.5cm}{\rm Pr} ( B_\nu \hspace {0.05cm}\vert \hspace {0.05cm}B_{\nu {\rm -1 } }, B_{\nu { -2 } }).$$

$\text{Example 2:}$  Natural languages are often describable by Markov chains,  although the order  $k$  tends here to infinity. 

In this example,  however,  texts are only approximated by second order Markov chains.

Synthetically generated texts  based on German or English book template

The graphic shows two synthetically generated texts:

  • The left text was synthetically generated starting from a German book template with bindings up to second order.
  • For the right text,  an English book template was used.


One recognizes despite the restriction to  $k = 2$ 

  1. many $($short$)$ German words on the left,
  2. many $($short$)$ English words on the right,
  3. German words are on the average longer than English words. 


There is no meaningful content,  but the structure of the respective language is recognizable.

First order Markov chain


In the following, we always restrict ourselves to the special case  $k =1$.

$\text{Definition:}$ 

$(1)$  In a  »first order Markov chain«  only the statistical binding to the last event is considered,  which in practice is usually the strongest.

$(2)$  For example:  A  »binary first order Markov chain«  ⇒   universal set  $G = \{ A, \ B \}$  has the following event probabilities at time  $\nu$:

$${\rm Pr}(A_\nu) = {\rm Pr}(A_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) ,$$
$${\rm Pr}(B_\nu) = {\rm Pr}(B_\nu \hspace{0.05cm} \vert \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} \vert \hspace{0.05cm}B_{\nu - 1}) \cdot {\rm Pr}(B_{\nu - 1}) .$$


Regarding these equations,  we note:

  • ${\rm Pr}(A_\nu)$  is shorthand for the probability that at time  $ν$  the event   $E_ν = A = \overline{B}$  occurs,  and it holds:
$${\rm Pr}(B_\nu) = 1 - {\rm Pr}(A_\nu).$$
  • At each time there are four transition probabilities  ${\rm Pr}(E_ν\hspace{0.05cm} |\hspace{0.05cm} E_{ν–1})$,  but only two of them are independent,  because it holds:
$${\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}),$$
$${\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}).$$
  • Generalizing this last statement:  For a Markov chain with  $M$ events,  there are exactly  $M · (M – 1)$  independent transition probabilities at each time  $ν$.


$\text{Example 3:}$  With the given transition probabilities

$${\rm Pr}(A_ν\hspace{0.05cm}\vert\hspace{0.05cm} A_{ν–1}) = 0.2, \hspace{0.5cm} {\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 0.4,$$

the other two transition probabilities are also uniquely specified:

$${\rm Pr}(B_ν\hspace{0.05cm} \vert\hspace{0.05cm} A_{ν–1}) = 1- 0.2 = 0.8, \hspace{0.5cm} {\rm Pr}(A_ν\hspace{0.05cm} \vert\hspace{0.05cm} B_{ν–1}) = 1- 0.4 = 0.6.$$

Homogeneous Markov chains


Applicability of Markov chains to practical problems is usually only given with further restrictive conditions.

$\text{Definition:}$ 

$(1)$  If all transition probabilities are independent of time  $ν$,  the Markov chain is  »homogeneous«.

$(2)$  In the case  $M = 2$  we use the following abbreviations:

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


First order homogeneous Markov chain

Thus,  the event probabilities of a binary homogeneous Markov chain:

$${\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}) .$$

These are absolute probabilities in contrast to the conditional transition probabilities.

We can also read from the Markov diagram:

  • The sum of the  »outgoing arrows«  of an event is always one:
$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A) + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) =1,$$
$${\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B) + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) =1.$$
  • For the sums of the  »incoming arrows«  this restriction does not apply:
$$ 0 < {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A) + {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}B)< 2,$$
$$0 < {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B)< 2.$$

Stationary probabilities


Important properties of random processes are  »$\text{stationarity}$«  and  »$\text{ergodicity}$«.  Although these terms are not defined until the fourth main chapter  »Random Variables with Statistical Dependence«,  we apply them here already in advance to Markov chains.

$\text{Definition:}$ 

$(1)$  If,  in addition to the transition probabilities,  all event probabilities of a Markov chain are independent of time  $ν$,  then the Markov chain is called  »stationary«. 

$(2)$  One then omits the index  $ν$  and writes in the binary case:

$${\rm Pr}(A_\nu ) = {\rm Pr}(A ), \hspace{0.5 cm} {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$

$(3)$  These quantities are also called  »ergodic probabilities«  of the Markov chain.


Stationary Markov chains have the special features mentioned below:

  • To calculate the ergodic probabilities of a binary Markov chain  $(M =2)$  one can use the following equations:
$${\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) .$$
  • Since these equations depend linearly on each other,  one may use only one of them.  As the second equation of determination one may use:
$${\rm Pr}(A) + {\rm Pr}(B) = 1.$$
  • The ergodic probabilities result from it to
$${\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}, $$
$${\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) }.$$

$\text{Example 4:}$  We consider a stationary and binary Markov chain with events  $A$  and $B$  and transition probabilities  ${\rm Pr}(A \hspace{0.05cm} \vert\hspace{0.05cm}A) = 0.4$  and  ${\rm Pr}(B \hspace{0.05cm} \vert \hspace{0.05cm}B) = 0.8$.

Transient response of the event probabilities $($three decimal places$)$

Furthermore,  we assume that each realization starts with event  $A$  at starting time  $ν = 0$.  We then obtain the event probabilities listed on the right:

In a strict sense,  this is a non-stationary Markov chain,  but it is  $($nearly$)$  settled after a short time:

  1. At later times  $(ν > 5),$  the event probabilities  ${\rm Pr}(A_ν) \approx 1/4$,  ${\rm Pr}(B_ν) \approx 3/4$  are no longer seriously changed.
  2. However,  from  ${\rm Pr}(A_{ν=5}) = 0.250$  and  ${\rm Pr}(B_{ν=5}) = 0.750$  it should not be concluded that the Markov chain is already perfectly steady at time   $ν = 5$.
  3. Indeed,  the exact values are: 
$${\rm Pr}(A_{ν=5}) = 0.25024,\hspace{0.5cm}{\rm Pr}(B_{ν=5}) = 0.74976.$$


$\text{Conclusion:}$  For a stationary Markov chain, the ergodic probabilities always occur with good approximation very long after the chain is switched on   $(ν → ∞)$ , regardless of the initial conditions  ${\rm Pr}(A_0)$  and  ${\rm Pr}(B_0) = 1 - {\rm Pr}(A_0)$.

Matrix vector representation


Homogeneous Markov chains can be represented very compactly with vectors and matrices.  This is especially recommended for more than two events:

$$E_\nu \in G = \{ E_{\rm 1},\ E_{\rm 2}, \hspace{0.1cm}\text{...}\hspace{0.1cm},\ E_\mu , \hspace{0.1cm}\text{...}\hspace{0.1cm},\ E_M \}.$$

For the matrix-vector representation,  we use the following nomenclature:

  • We summarize the  $M$  probabilities at time  $ν$  in a column vector:
$${\mathbf{p}^{(\nu)}} = \left[ \begin{array}{c} {p_{\rm 1}}^{(\nu)} \\ \dots \\ {p_{M}}^{(\nu)} \end{array} \right] \hspace{0.5cm}{\rm with} \hspace{0.5cm} {p_{\mu}}^{(\nu)} = {\rm Pr}(E_\nu = E_\mu ).$$
  • The transition probabilities are expressed by an  $M \times M$ matrix:
$${\mathbf{P}} =\left( p_{ij} \right) = \left[ \begin{array}{cccc} p_{11} & p_{12} & \cdots & p_{1M} \\ p_{21} & p_{22}& \cdots & p_{2M} \\ \dots & \dots & \dots & \dots \\ p_{M1} & p_{M2} & \cdots & p_{MM} \end{array} \right] \hspace{0.5cm}{\rm with} \hspace{0.5cm} {p_{ij}} = {\rm Pr}(E_{\nu +1 } = E_j \hspace{0.05cm}| \hspace{0.05cm} E_{\nu } = E_i).$$

The accompanying figure illustrates this nomenclature using the example  $M = 2$.  The new event probability vector after one step is:

To denote the transition probabilities
$${\mathbf{p}^{(\nu + 1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(\nu )}} .$$

Here,  ${\mathbf{P}^{\rm T}}$  denotes the  »transposed matrix»  to  $\mathbf{P}$.  Thus,  after  $n$  steps,  the result is

$${\mathbf{p}^{(\nu +{\it n})}} = \left( {\mathbf{P}}^{\rm T} \right)^n \cdot {\mathbf{p}^{(\nu )}} .$$

In the limit transition  $(n → ∞)$  one then always achieves stationarity of the Markov chain:

$$\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}} \\ \dots \\ {p_{M}} \end{array} \right] .$$

$\text{Definition:}$  Multiplying the transition matrix  ${\mathbf{P} }$  infinitely many times by itself and denoting the result by  ${\mathbf{P} }_{\rm erg}$,  the resulting matrix consists of  $M$  equal rows:

$${\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} \\ \dots & \dots & \dots & \dots \\ p_{1} & p_{2} & \cdots & p_{M} \end{array} \right] .$$

The probabilities  $p_1, \hspace{0.15cm}\text{...}\hspace{0.15cm}, p_M$  in each of these lines are called the  »ergodic probabilities«.


$\text{Example 5:}$  We consider a Markov chain with the events  $E_1,  E_2$  and  $E_3$   ⇒   $M=3$.  The graph shows

Markov diagram with three events
  • on the left the Markov diagram,
  • on the upper right the transition matrix  $\mathbf{P}$,
  • below their powers  $\mathbf{P}^2$  and  $\mathbf{P}^3$.


In the Markov diagram,  all transition probabilities with the numerical value  $1/2$  are shown in blue;   green indicates the probability  $1/4$.

  • At the start  $(ν =0)$  all events are equally probable.  For  $ν = 1$  then holds:
$${\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] .$$
From this it can be seen that we get from the matrix  $\mathbf{P}$  to the transposed matrix  ${\mathbf{P}^{\rm T} }$  by exchanging rows and columns.
  • At time  $ν =2$  $($and also at all later times$)$  the same probabilities result:
$${\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] .$$
This means:  The ergodic probabilities of the three events are  $1/2$  $($for  $E_1)$,  $1/4$  $($for  $E_2)$,  and $1/4$  $($for  $E_3)$.
  • This result could have been read directly from the ergodic matrix:
$${\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] .$$
This is obtained by continuously multiplying the transition matrix by itself.
  • In the figure above the powers  $\mathbf{P}^2$  and  $\mathbf{P}^3$  are given,  which approximate the matrix  $\mathbf{P}_{\rm erg}$.

Exercises for the chapter

Exercise 1.6: Transition Probabilities

Exercise 1.6Z: Ergodic Probabilities

Exercise 1.7: Ternary Markov Chain

Exercise 1.7Z: BARBARA Generator