Theory of Stochastic Signals/Markov Chains - Revision history

Guenter at 11:51, 6 February 2024

2024-02-06T11:51:59Z

Guenter at 16:30, 5 February 2024

2024-02-05T16:30:15Z

Guenter at 16:07, 5 February 2024

2024-02-05T16:07:40Z

Show changes

Guenter at 14:17, 13 December 2022

2022-12-13T14:17:27Z

Hwang at 21:28, 11 December 2022

2022-12-11T21:28:13Z

Hwang at 21:24, 11 December 2022

2022-12-11T21:24:19Z

Hwang at 21:19, 11 December 2022

2022-12-11T21:19:21Z

Noah at 14:35, 13 April 2022

2022-04-13T14:35:22Z

Noah at 17:16, 11 April 2022

2022-04-11T17:16:02Z

Guenter at 15:25, 1 December 2021

2021-12-01T15:25:32Z

@@ Line 205: / Line 205: @@
 :$${\mathbf{p}^{(\nu + 1)}} = {\mathbf{P}}^{\rm T} \cdot {\mathbf{p}^{(\nu )}} .$$
-Here,&nbsp; ${\mathbf{P}^{\rm T}}$&nbsp; denotes the&nbsp; "transposed matrix"&nbsp; to&nbsp; $\mathbf{P}$.&nbsp; Thus,&nbsp; after&nbsp; $n$&nbsp; steps,&nbsp; the result is
+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 )}} .$$
@@ Line 229: / Line 229: @@
 *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] .$$
-: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 the rows and columns.
+: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.
 *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] .$$
 :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)$.

@@ Line 7: / Line 7: @@
 ==Considered scenario==
 <br>
 [[File:En_Sto_T_1_4_S1.png |right|frame|Possible events and event sequence]]
-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:
 :$$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 \}.$$
@@ Line 152: / Line 153: @@
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-*If,&nbsp; in addition to the transition probabilities,&nbsp; all event probabilities of a Markov chain are independent of the time&nbsp; $ν$,&nbsp; then the Markov chain is called&nbsp; &raquo;'''stationary'''&laquo;.&nbsp; One then omits the index&nbsp; $ν$&nbsp; and writes in the binary case:
 :$${\rm Pr}(A_\nu ) = {\rm Pr}(A ),  \hspace{0.5 cm}  {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$
-*These quantities are also called the&nbsp; &raquo;'''ergodic probabilities'''&laquo;&nbsp; of the Markov chain.}}
+$(3)$&nbsp; These quantities are also called&nbsp; &raquo;'''ergodic probabilities'''&laquo;&nbsp; of the Markov chain.}}
@@ Line 162: / Line 166: @@
 :$${\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,&nbsp; one may use only one of them.&nbsp;  For example,&nbsp; as the second equation of determination one may use:
+*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.$$
@@ Line 170: / Line 174: @@
 {{GraueBox|TEXT=
-$\text{Example 4:}$&nbsp; We consider a 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$.
+$\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]]
+[[File:P_ID642__Sto_T_1_4_S5_neu.png |right|frame| Transient response of the event probabilities $($three decimal places$)$]]
-*Furthermore,&nbsp; we assume that each realization of this chain starts with event&nbsp; $A$&nbsp; at the starting time&nbsp; $ν = 0$&nbsp;.
-*We then obtain the event probabilities listed below&nbsp; (with three decimal places):
+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:
-In a strict sense,&nbsp; this is a non-stationary Markov chain, but it is&nbsp; (nearly)&nbsp; settled after a short time:
+In a strict sense,&nbsp; this is a non-stationary Markov chain,&nbsp; but it is&nbsp; $($nearly$)$&nbsp; settled after a short time:
-*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.
+#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.
-*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$.
+#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$.
-*Indeed,&nbsp; the exact values are&nbsp; ${\rm Pr}(A_{ν=5}) = 0.25024$&nbsp; and&nbsp; ${\rm Pr}(B_{ν=5}) = 0.74976$.}}
+#Indeed,&nbsp; the exact values are:&nbsp;
 {{BlaueBox|TEXT=
-$\text{Conclusion:}$&nbsp;
+$\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)$.
 }}

@@ Line 134: / Line 134: @@
 :$$0 < {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B)< 2.$$
-You can calculate and display the transient behavior of the event probabilities of such a binary Markov chain with the&nbsp;  (German language)&nbsp; interactive SWF applet
+&rArr; &nbsp; You can calculate and display the transient behavior of the event probabilities of such a binary Markov chain with the&nbsp;  (German language)&nbsp; interactive SWF applet
 : [[Applets:Markovketten|"Ereigniswahrscheinlichkeiten einer Markov-Kette erster Ordnung"]] &nbsp; &rArr; &nbsp; "Event Probabilities of a First Order Markov Chain".

@@ Line 68: / Line 68: @@
 $\text{Example 2:}$&nbsp; Natural languages are often describable by Markov chains,&nbsp; although the order&nbsp; $k$&nbsp; tends to infinity.&nbsp;
-In this example,&nbsp; however,&nbsp; texts are only approximated by second-order Markov chains.
+In this example,&nbsp; however,&nbsp; texts are only approximated by second order Markov chains.
 The graphic shows two synthetically generated texts:

@@ Line 43: / Line 43: @@
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-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; $ν$
+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;&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.}}

@@ Line 21: / Line 21: @@
-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;
+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|"Random Processes"]].&nbsp;
 {{GraueBox|TEXT=
@@ Line 43: / Line 43: @@
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-A&nbsp; $k$-th order&nbsp; '''Markov Chain'''&nbsp; serves as a model for time- and value-discrete processes,&nbsp; where the event probabilities at time&nbsp; $ν$
+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;&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.}}
@@ Line 85: / Line 85: @@
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-*In a&nbsp;  '''First Order Markov Chain'''&nbsp; only the statistical binding to the last event is considered,&nbsp; which in practice is usually the strongest.
+*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.
 *A binary first order Markov chain &nbsp;  ⇒  &nbsp; universal set&nbsp; $G = \{ A, \ B \}$&nbsp; has the following event probabilities at time&nbsp; $\nu$:
@@ Line 113: / Line 113: @@
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-*If all transition probabilities are independent of the time&nbsp; $ν$,&nbsp; the Markov chain is&nbsp; '''homogeneous'''.
+*If all transition probabilities are independent of the time&nbsp; $ν$,&nbsp; the Markov chain is&nbsp; &raquo;'''homogeneous'''&laquo;.
 *In the case&nbsp; $M = 2$&nbsp; we use the following abbreviations for this:
@@ Line 126: / Line 126: @@
 We can also read from the Markov diagram:
-*The sum of the&nbsp; '''outgoing arrows'''&nbsp; of an event is always one
+*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}B)  + {\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) =1.$$
-*For the sums of the&nbsp; '''incoming arrows'''&nbsp; this restriction does not apply:
+*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.$$
 You can calculate and display the transient behavior of the event probabilities of such a binary Markov chain with the&nbsp;  (German language)&nbsp; interactive SWF applet
-: [[Applets:Markovketten|Ereigniswahrscheinlichkeiten einer Markov-Kette erster Ordnung]] &nbsp; &rArr; &nbsp; "Event Probabilities of a First Order Markov Chain".
+: [[Applets:Markovketten|"Ereigniswahrscheinlichkeiten einer Markov-Kette erster Ordnung"]] &nbsp; &rArr; &nbsp; "Event Probabilities of a First Order Markov Chain".
 ==Stationary probabilities==
 <br>
-Important properties of random processes are&nbsp;  [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Stationary_random_processes|stationarity]]&nbsp;  and&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Ergodic_random_processes|ergodicity]].&nbsp; Although these terms are not defined until the fourth main chapter&nbsp; "Random Variables with Statistical Dependence",&nbsp; we apply them here already in advance to Markov chains.
+Important properties of random processes are&nbsp;  [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Stationary_random_processes|$\text{stationarity}$]]&nbsp;  and&nbsp; [[Theory_of_Stochastic_Signals/Auto-Correlation_Function_(ACF)#Ergodic_random_processes|$\text{ergodicity}$]].&nbsp; Although these terms are not defined until the fourth main chapter&nbsp; "Random Variables with Statistical Dependence",&nbsp; we apply them here already in advance to Markov chains.
 {{BlaueBox|TEXT=
 $\text{Definition:}$&nbsp;
-*If,&nbsp; in addition to the transition probabilities,&nbsp; all event probabilities of a Markov chain are independent of the time&nbsp; $ν$,&nbsp; then the Markov chain is called&nbsp; '''stationary'''.&nbsp; One then omits the index&nbsp; $ν$&nbsp; and writes in the binary case:
+*If,&nbsp; in addition to the transition probabilities,&nbsp; all event probabilities of a Markov chain are independent of the time&nbsp; $ν$,&nbsp; then the Markov chain is called&nbsp; &raquo;'''stationary'''&laquo;.&nbsp; One then omits the index&nbsp; $ν$&nbsp; and writes in the binary case:
 :$${\rm Pr}(A_\nu ) = {\rm Pr}(A ),  \hspace{0.5 cm}  {\rm Pr}(B_\nu ) = {\rm Pr}(B).$$
-*These quantities are also called the&nbsp; '''ergodic probabilities'''&nbsp; of the Markov chain.}}
+*These quantities are also called the&nbsp; &raquo;'''ergodic probabilities'''&laquo;&nbsp; of the Markov chain.}}
@@ Line 202: / Line 202: @@
 $\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] .$$
-The probabilities&nbsp; $p_1, \hspace{0.15cm}\text{...}\hspace{0.15cm}, p_M$&nbsp; in each of these lines are called the&nbsp; '''ergodic probabilities'''. }}
+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;. }}

@@ Line 18: / Line 18: @@
 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&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.
-*This statement also means that in this chapter we consider a&nbsp; '''sequence of events with internal statistical ties'''.
+*This statement also means that in this chapter we consider a&nbsp; '''sequence of events with internal statistical bindings'''.