Difference between revisions of "Aufgaben:Exercise 1.6: Transition Probabilities"

From LNTwww
 
(23 intermediate revisions by 5 users not shown)
Line 1: Line 1:
  
−
{{quiz-Header|Buchseite=Stochastische Signaltheorie/Markovketten
+
{{quiz-Header|Buchseite=Theory_of_Stochastic_Signals/Markov_Chains
 
}}
 
}}
  
−
[[File:P_ID451__Sto_A_1_6.png|right|]]
+
[[File:EN_Sto_A_1_6.png|right|frame|$20$  Realizations of the considered Markov chain]]
−
Rechts sehen Sie 20 Realisierungen einer binären homogenen Markovkette erster Ordnung mit den Ereignissen $A$ und $B$. Man erkennt bereits aus dieser Darstellung, dass zu Beginn ($ν = 0$) das Ereignis $A$ überwiegt, zu späteren Zeitpunkten – etwa ab $ν = 4$ – jedoch etwas häufiger das Ereignis $B$ eintritt.
+
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.
  
−
Durch Mittelung über Millionen von Realisierungen wurden einige Ereigniswahrscheinlichkeiten numerisch ermittelt:
 
  
−
$Pr(A_\text{v=0}) \approx 0.9; Pr(A_\text{v=1}) \approx 0.15; Pr(A_\text{v>4}) \approx 0.4$
+
By averaging over millions of realizations,  some event probabilities were determined numerically:
  
−
Diese empirischen Zahlenwerte sollen herangezogen werden, um die Parameter (Übergangswahrscheinlichkeiten) der Markovkette zu ermitteln.
+
:$${\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.
  
  
  
−
'''Hinweis''': Die Aufgabe bezieht sich auf die theoretischen Grundlagen von Kapitel 1.4. Sie können Ihre Ergebnisse mit dem nachfolgenden Berechnungstool überprüfen:
 
  
  
  
−
===Fragebogen===
+
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>
−
{Welche Wahrscheinlichkeiten ergeben sich zu den Zeiten $ν = 0$, $ν = 1$ und $ν = 9$, wenn man nur die 20 dargestellten Realisierungen berücksichtigt?
+
{What are the probabilities at times&nbsp; $ν = 0$, &nbsp; $ν = 1$ &nbsp; and&nbsp; $ν = 9$, given&nbsp; only the&nbsp; $20$&nbsp; realizations shown?
 
|type="{}"}
 
|type="{}"}
−
$Pr(A_\text{v=0})$ = { 0.85 3% }
+
${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}0}) \ = \ $ { 0.85 3% }
−
$Pr(A_\text{v=1})$ = { 0.1 3% }
+
${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}1}) \ = \ $ { 0.1 3% }
−
$Pr(A_\text{v=9})$ = { 0.4 3% }
+
${\rm Pr}(A_{\nu \hspace{0.05cm} = \hspace{0.05cm}9}) \ = \ $ { 0.4 3% }
  
−
{Welche der Aussagen sind aufgrund der Musterfolgen zutreffend?
+
{Based on the pattern sequences,&nbsp; which of the statements are true?
 
|type="[]"}
 
|type="[]"}
−
+ Nach $A$ ist $B$ wahrscheinlicher als $A$.
+
+ After&nbsp; $A$:&nbsp; $B$&nbsp; is more probable than&nbsp; $A$.
−
+ Sowohl nach $A$ als auch nach $B$ kann wieder $A$ oder $B$ folgen.
+
+ After both&nbsp; $A$&nbsp; and&nbsp; $B$:&nbsp; $A$&nbsp; or&nbsp; $B$&nbsp; can follow again.
−
- Die Folge $B B B B ...$ ist nicht möglich.
+
- The sequence&nbsp; "$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{...}$"&nbsp; is not possible.
  
−
{Berechnen Sie alle Übergangswahrscheinlichkeiten der Markovkette. Wie groß sind insbesondere $Pr(A | A)$ und $Pr(B | B)$?
+
{Calculate all transition probabilities of the Markov chain.&nbsp; In particular,&nbsp; how large are&nbsp; ${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A)$&nbsp; and&nbsp; ${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B)$?
 
|type="{}"}
 
|type="{}"}
−
$Pr(A|A)$ = { 0.1 3% }
+
${\rm Pr}(A\hspace{0.05cm} | \hspace{0.05cm}A) \ = \ $ { 0.1 3% }
−
$Pr(B|B)$ = { 0.4 3% }
+
${\rm Pr}(B\hspace{0.05cm} | \hspace{0.05cm}B) \ = \ $ { 0.4 3% }
  
−
{Wie groß ist die Wahrscheinlichkeit, dass die ersten zehn Elemente der Folge jeweils $B$ sind?
+
{What is the probability that the first ten elements of the sequence are each&nbsp; $B$&nbsp;?
 
|type="{}"}
 
|type="{}"}
−
$Pr(B_0, ... , B_9)$ = { 2.62 3% } $* 10^{}$^{ -5 }  
+
${\rm Pr}(B_0, \hspace{0.05cm}\text{...}\hspace{0.05cm} , B_9)\ = \ $ { 2.62 3% } $\ \cdot  10^{-5}$
  
  
−
{Wie groß ist die Wahrscheinlichkeit, dass sehr lange nach Einschalten der Kette die Zeichenfolge $A B B A$ erzeugt wird?
+
{What is the probability that the string&nbsp; "$A\hspace{-0.05cm}-\hspace{-0.05cm}B \hspace{-0.05cm}-\hspace{-0.05cm}B\hspace{-0.05cm}-\hspace{-0.05cm}A$"&nbsp; is generated a very long time after the chain is switched on?
 
|type="{}"}
 
|type="{}"}
−
$Pr(A B B A)$ = { 0.0864 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% } $\ \%$
  
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''1.'''
+
'''(1)'''&nbsp; The corresponding probabilities are:
−
'''2.'''
+
 
−
'''3.'''
+
:$${\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}.$$
−
'''4.'''
+
 
−
'''5.'''
+
 
−
'''6.'''
+
'''(2)'''&nbsp; <u>Proposed solutions 1 and 2</u> are correct:
−
'''7.'''
+
*$A$&nbsp; is followed by&nbsp; $B$&nbsp; much more frequently than by&nbsp; $A$,&nbsp; that is,&nbsp; it will certainly be&nbsp; ${\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&nbsp; $A$&nbsp; and&nbsp; $B$&nbsp; are possible.&nbsp; It follows that all four transition probabilities will be nonzero.
 +
*Because of&nbsp; ${\rm Pr}(B_\text{v=0})  \ne 0$&nbsp; and&nbsp; ${\rm Pr}(B \hspace{0.05cm} | \hspace{0.05cm}B) \ne 0$,&nbsp; the sequence&nbsp; "$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}...$"&nbsp; can of course also be generated,&nbsp; even though it is not present in the twenty Markov chains output here.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; For a first-order Markov chain,&nbsp; with the abbreviations&nbsp; ${\rm Pr}(A_0) = {\rm Pr}(A_{\nu=0})$&nbsp;  and&nbsp; ${\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&nbsp; ${\rm Pr}(A) = {\rm Pr}(A_{\nu \hspace{0.05cm} > \hspace{0.05cm}4}) = 0.4$&nbsp; and&nbsp; ${\rm Pr}(B) = {\rm Pr}(B_{\nu \hspace{0.05cm} > \hspace{0.05cm}4}) = 0.6$.&nbsp; 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,&nbsp; 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&nbsp; $6$&nbsp; 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,&nbsp; we get&nbsp; $ {\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)'''&nbsp; This case is only possible if the Markov chain starts with&nbsp; $B$&nbsp; and then there are nine transitions from&nbsp; $B$&nbsp; to&nbsp; $B$&nbsp;:
 +
:$${\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)'''&nbsp; Here we have to assume the ergodic probability&nbsp; ${\rm Pr}(A)$&nbsp; 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 \% }.$$
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
−
[[Category:Aufgaben zu Stochastische Signaltheorie|^1.4 Markovketten^]]
+
[[Category:Theory of Stochastic Signals: Exercises|^1.4 Markov Chains^]]

Latest revision as of 21:33, 19 December 2021

$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:

  • 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 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 \% }.$$

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_1.6:_Transition_Probabilities&oldid=44212"
  • Powered by MediaWiki