Aufgaben:Exercise 1.6: Transition Probabilities

• Return to book

$20$  Realizations of the considered Markov chain

On the right you see  $20$  realizations of a binary homogeneous Markov chain of first order with the events  $A$  and  $B$:

• One can already see from this representation that at the beginning  $(ν = 0)$  event  $A$  predominates.
• However,  at later times,  approximately from  $ν = 4$:  The event  $B$  occurs somewhat more frequently.

By averaging over millions of realizations,  some event probabilities were determined numerically:

$${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}0}) \approx 0.9, \hspace{0.3cm}{\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}1}) \approx 0.15, \hspace{0.3cm} {\rm Pr}(A_{\nu \hspace{0.05cm} > \hspace{0.05cm}4}) \approx 0.4.$$

These empirical numerical values will be used to determine (approximately) the  "transition probabilities"  of the Markov chain.

Hints:

• The exercise belongs to the chapter  Markov Chains.

• You can check your results with the   (German language)  interactive SWF applet

Ereigniswahrscheinlichkeiten einer Markov-Kette erster Ordnung   ⇒   "Event Probabilities of a First Order Markov Chain".

Questions

1 What are the probabilities at times  $ν = 0$,   $ν = 1$   and  $ν = 9$, given  only the  $20$  realizations shown?

${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}0}) \ = \ $

${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}1}) \ = \ $

${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}9}) \ = \ $

2 Based on the pattern sequences,  which of the statements are true?

	After  $A$:  $B$  is more probable than  $A$.
	After both  $A$  and  $B$:  $A$  or  $B$  can follow again.
	The sequence  "$B\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}\text{...}$"  is not possible.

3 Calculate all transition probabilities of the Markov chain.  In particular,  how large are  ${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A)$  and  ${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B)$?

${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A) \ = \ $

${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B) \ = \ $

4 What is the probability that the first ten elements of the sequence are each  $B$ ?

${\rm Pr}(B_0, \hspace{0.05cm}\text{...}\hspace{0.05cm} , B_9)\ = \ $ $\ \cdot 10^{-5}$

5 What is the probability that the string  "$A\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}A$"  is generated a very long time after the chain is switched on?

${\rm Pr}(A\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}A)\ = \ $ $\ \%$

Solution

Solution

(1)  The corresponding probabilities are:

$${\rm Pr}(A_{\nu=0}) = 17/20 \;\underline{= 0.85}, \hspace{0.2cm} {\rm Pr}(A_{\nu=1}) = 2/20 \;\underline{= 0.10}, \hspace{0.2cm} {\rm Pr}(A_{\nu=9}) = 8/20 \;\underline{= 0.40}.$$

(2)  Proposed solutions 1 and 2 are correct:

• $A$  is followed by  $B$  much more frequently than  $A$, that is, it will certainly be  ${\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}A) > {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm}A)$ .
• All four transitions between the two events  $A$  and  $B$  are possible.  It follows that all four transition probabilities will be nonzero.
• Because of  ${\rm Pr}(B_\text{v=0}) \ne 0$  and  ${\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) \ne 0$ , the sequence  "$B\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{0.15cm}...$"  can of course also be generated, even though it is not present in the twenty Markov chains output here.

(3)  For a first-order Markov chain, with the abbreviations  ${\rm Pr}(A_0) = {\rm Pr}(A_{\nu=0})$  and  ${\rm Pr}(A_1) = {\rm Pr}(A_{\nu=1})$:

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

• The ergodic probabilities are  ${\rm Pr}(A) = {\rm Pr}(A_{\nu \hspace{0.05cm} > \hspace{0.05cm}4}) = 0.4$  and  ${\rm Pr}(B) = {\rm Pr}(B_{\nu \hspace{0.05cm} > \hspace{0.05cm}4}) = 0.6$.  The following relationship exists between these:

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

• With the numerical values given, we obtain from these last two equations:

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

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

• Multiplying the first equation by  $6$  and subtracting the second from it gives:

$$0.5 = 5 \cdot {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm} A) \hspace{0.15cm} \Rightarrow

\hspace{0.15cm} {\rm Pr}(A \hspace{0.05cm} | \hspace{0.05cm} A) \hspace{0.15cm}\underline {= 0.1}.$$

• Substituting this result into one of the upper equations, we get  $ {\rm Pr}(A\hspace{0.05cm}|\hspace{0.05cm}B) = 0.6$. The other probabilities are:

$${\rm Pr}(B\hspace{0.05cm}|\hspace{0.05cm}A) = 1 - {\rm Pr}(A\hspace{0.05cm}|\hspace{0.05cm}A) = 0.9, \hspace{0.3cm}

{\rm Pr}(B\hspace{0.05cm}|\hspace{0.05cm}B) = 1 - {\rm Pr}(A\hspace{0.05cm}|\hspace{0.05cm}B)\ \underline{= 0.4}.$$

(4)  This case is only possible if the Markov chain starts with  $B$  and then there are nine transitions from  $B$  to  $B$ :

$${\rm Pr}(B_0,\hspace{0.05cm}\text{...} \hspace{0.05cm}, B_{9}) = {\rm Pr}(B_0) \cdot {\rm Pr}(B\hspace{0.05cm}| \hspace{0.05cm} B)^9 = {\rm 0.1} \cdot {\rm 0.4}^9 \hspace{0.15cm}\underline {\approx 2.62 \cdot 10^{-5}}. $$

(5)  Here we have to assume the ergodic probability  ${\rm Pr}(A)$  and we obtain:

$${\rm Pr}(A_{\nu}, \hspace{0.05cm}B_{\nu +1}, \hspace{0.05cm}B_{\nu +2},\hspace{0.05cm} A_{\nu +3}) = {\rm Pr}(A) \hspace{0.01cm}\cdot \hspace{0.01cm}{\rm Pr}(B\hspace{0.05cm}| \hspace{0.05cm} A) \hspace{0.01cm}\cdot\hspace{0.01cm} {\rm Pr}(B\hspace{0.05cm}| \hspace{0.05cm} B)\hspace{0.01cm}\cdot \hspace{0.01cm}{\rm Pr}(A\hspace{0.05cm}| \hspace{0.05cm} B)\hspace{0.15cm}\underline {\approx 8.64 \% }.$$