Difference between revisions of "Aufgaben:Exercise 1.6: Transition Probabilities"
(13 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Theory_of_Stochastic_Signals/Markov_Chains |
}} | }} | ||
− | [[File: | + | [[File:EN_Sto_A_1_6.png|right|frame|$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.$$ | :$${\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. | |
Line 20: | Line 20: | ||
− | + | Hints: | |
− | * | + | *The exercise belongs to the chapter [[Theory_of_Stochastic_Signals/Markov_Chains|Markov Chains]]. |
− | * | + | *You can check your results with the (German language) interactive SWF applet |
+ | : [[Applets:Markovketten|Ereigniswahrscheinlichkeiten einer Markov-Kette erster Ordnung]] ⇒ "Event Probabilities of a First Order Markov Chain". | ||
− | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {What are the probabilities at times $ν = 0$, $ν = 1$ and $ν = 9$, given only the $20$ realizations shown? |
|type="{}"} | |type="{}"} | ||
${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}0}) \ = \ $ { 0.85 3% } | ${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}0}) \ = \ $ { 0.85 3% } | ||
Line 36: | Line 37: | ||
${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}9}) \ = \ $ { 0.4 3% } | ${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}9}) \ = \ $ { 0.4 3% } | ||
− | { | + | {Based on the pattern sequences, which of the statements are true? |
|type="[]"} | |type="[]"} | ||
− | + | + | + 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. |
− | { | + | {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)$? |
|type="{}"} | |type="{}"} | ||
${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A) \ = \ $ { 0.1 3% } | ${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A) \ = \ $ { 0.1 3% } | ||
${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B) \ = \ $ { 0.4 3% } | ${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B) \ = \ $ { 0.4 3% } | ||
− | { | + | {What is the probability that the first ten elements of the sequence are each $B$ ? |
|type="{}"} | |type="{}"} | ||
${\rm Pr}(B_0, \hspace{0.05cm}\text{...}\hspace{0.05cm} , B_9)\ = \ $ { 2.62 3% } $\ \cdot 10^{-5}$ | ${\rm Pr}(B_0, \hspace{0.05cm}\text{...}\hspace{0.05cm} , B_9)\ = \ $ { 2.62 3% } $\ \cdot 10^{-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? |
|type="{}"} | |type="{}"} | ||
${\rm Pr}(A\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}A)\ = \ $ { 8.64 3% } $\ \%$ | ${\rm Pr}(A\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}A)\ = \ $ { 8.64 3% } $\ \%$ | ||
Line 58: | Line 59: | ||
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' The corresponding probabilities are: |
− | :$${\rm Pr}(A_\ | + | :$${\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)''' <u>Proposed solutions 1 and 2</u> are correct: | ||
+ | *$A$ is followed by $B$ much more frequently than by $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)''' | + | |
+ | |||
+ | '''(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).$$ | :$${\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).$$ | :$${\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.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 .$$ | :$$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 | :$$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}.$$ | \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}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}.$$ | {\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)''' | + | |
+ | |||
+ | '''(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}}. $$ | :$${\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)''' | + | |
+ | |||
+ | '''(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 \% }.$$ | :$${\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 \% }.$$ | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Line 93: | Line 100: | ||
− | [[Category: | + | [[Category:Theory of Stochastic Signals: Exercises|^1.4 Markov Chains^]] |
Latest revision as of 21:33, 19 December 2021
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
Solution
- $${\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 by $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 \% }.$$