Aufgaben:Aufgabe 1.7Z: BARBARA-Generator: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 2: Zeile 2:
 
{{quiz-Header|Buchseite=Stochastische Signaltheorie/Markovketten}}
 
{{quiz-Header|Buchseite=Stochastische Signaltheorie/Markovketten}}
  
[[Datei:P_ID454__Sto_Z_1_7.png|right|frame|BARBARA-Generator]]
+
[[Datei:P_ID454__Sto_Z_1_7.png|right|frame|$\rm BARBARA$-Generator]]
Betrachtet wird hier ein ternärer Zufallsgenerator mit den Symbolen $A$, $B$ und $R$, der durch eine homogene und stationäre Markovkette erster Ordnung beschrieben werden kann.
+
Betrachtet wird hier ein ternärer Zufallsgenerator mit den Symbolen  $A$,  $B$  und  $R$, der durch eine homogene und stationäre Markovkette erster Ordnung beschrieben werden kann.
  
Die Übergangswahrscheinlichkeiten können dem skizzierten Markovdiagramm entnommen werden. Für die ersten drei Teilaufgaben soll stets $p = 1/4$ gelten.
+
*Die Übergangswahrscheinlichkeiten können dem skizzierten Markovdiagramm entnommen werden.  
 +
*Für die ersten drei Teilaufgaben soll stets  $p = 1/4$  gelten.
  
  
  
''Hinweis:''
+
 
*Die Aufgabe gehört zum  Kapitel [[Stochastische_Signaltheorie/Markovketten|Markovketten]].
+
 
 +
 
 +
Hinweis:  
 +
*Die Aufgabe gehört zum  Kapitel  [[Stochastische_Signaltheorie/Markovketten|Markovketten]].
 
   
 
   
  
Zeile 19: Zeile 23:
 
{Welche der nachfolgenden Aussagen sind zutreffend?
 
{Welche der nachfolgenden Aussagen sind zutreffend?
 
|type="[]"}
 
|type="[]"}
- Die Werte von $p > 0$ und $q < 1$ sind weitgehend frei wählbar.
+
- Die Werte von&nbsp; $p > 0$&nbsp; und&nbsp; $q < 1$&nbsp; sind weitgehend frei wählbar.
 
+ Für die Übergangswahrscheinlichkeiten muss gelten: &nbsp; $p + q = 1$.
 
+ Für die Übergangswahrscheinlichkeiten muss gelten: &nbsp; $p + q = 1$.
 
+ Alle Symbole haben gleiche ergodische Wahrscheinlichkeiten.
 
+ Alle Symbole haben gleiche ergodische Wahrscheinlichkeiten.
- Es gilt hier: ${\rm Pr}(A) = 1/2, \; {\rm Pr}(B) = 1/3, \; {\rm Pr}(R) = 1/6$.
+
- Es gilt hier:&nbsp; ${\rm Pr}(A) = 1/2, \; {\rm Pr}(B) = 1/3, \; {\rm Pr}(R) = 1/6$.
  
{Wie groß sind die bedingten Wahrscheinlichkeiten $p_{\rm A}$, $p_{\rm B}$ und $p_{\rm C}$, dass im Zeitbereich zwischen $ν+1$ und $ν+7$  die Sequenz $\rm BARBARA$ ausgegeben wird, wenn man sich zum Zeitpunkt $ν$ im Zustand $A$, $B$ bzw. $R$ befindet? Es gelte $p = 1/4$.
+
{Wie groß sind die bedingten Wahrscheinlichkeiten&nbsp; $p_{\rm A}$,&nbsp; $p_{\rm B}$&nbsp; und&nbsp; $p_{\rm C}$,&nbsp; dass zu den Zeiten zwischen&nbsp; $ν+1$&nbsp; und&nbsp; $ν+7$&nbsp; die Sequenz&nbsp; $BARBARA$&nbsp; ausgegeben wird, <br>wenn man sich zum Zeitpunkt&nbsp; $ν$&nbsp; im Zustand&nbsp; $A$,&nbsp; $B$&nbsp; bzw.&nbsp; $R$&nbsp; befindet?&nbsp; Es gelte&nbsp; $p = 1/4$.
 
|type="{}"}
 
|type="{}"}
 
$p_{\rm A} \ = \ $  { 0.549 3% } $\ \cdot 10^{-3}$  
 
$p_{\rm A} \ = \ $  { 0.549 3% } $\ \cdot 10^{-3}$  
Zeile 30: Zeile 34:
 
$p_{\rm C} \ = \ $ { 0.183 3% } $\ \cdot 10^{-3}$  
 
$p_{\rm C} \ = \ $ { 0.183 3% } $\ \cdot 10^{-3}$  
  
{Wie groß ist die Wahrscheinlichkeit insgesamt, dass der Generator zu sieben aufeinanderfolgenden Zeitpunkten die Sequenz $BARBARA$ ausgibt?<br>  Es gelte weiter $p = 1/4.$
+
{Wie groß ist die Wahrscheinlichkeit insgesamt, dass der Generator zu sieben aufeinanderfolgenden Zeitpunkten die Sequenz&nbsp; "$\rm BARBARA$"&nbsp; ausgibt?<br>  Es gelte weiter&nbsp; $p = 1/4.$
 
|type="{}"}
 
|type="{}"}
$p = 1/4\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(BARBARA)\ = \ $ { 0.244 3% } $\ \cdot 10^{-3}$
+
${\rm Pr}(\rm BARBARA)\ = \ $ { 0.244 3% } $\ \cdot 10^{-3}$
  
{Wie ist der Parameter $p_{\rm opt}$ zu wählen, damit ${\rm Pr}(BARBARA)$ möglichst groß wird? Welche Wahrscheinlichkeit ergibt sich damit für $\rm BARBARA$?
+
{Wie ist der Parameter&nbsp; $p_{\rm opt}$&nbsp; zu wählen, damit&nbsp; ${\rm Pr}(\rm BARBARA)$&nbsp; möglichst groß wird? <br>Welche Wahrscheinlichkeit ergibt sich damit für&nbsp; "$\rm BARBARA$"?
 
|type="{}"}
 
|type="{}"}
 
$p_{\rm opt} \ = \ $  { 0.8333 3% }
 
$p_{\rm opt} \ = \ $  { 0.8333 3% }
$p = p_{\rm opt}\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(BARBARA)\ = \ $ { 22 3% } $\ \cdot 10^{-3}$
+
$p = p_{\rm opt}\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(\rm BARBARA)\ = \ $ { 22 3% } $\ \cdot 10^{-3}$
  
 
</quiz>
 
</quiz>
Zeile 43: Zeile 47:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Richtig sind <u>der zweite und der dritte Lösungsvorschlag</u>:
+
'''(1)'''&nbsp; Richtig sind&nbsp; <u>der zweite und der dritte Lösungsvorschlag</u>:
*Die Summe aller abgehenden Pfeile muss immer $1$ sein. Deshalb gilt $q = 1 - p$.  
+
*Die Summe aller abgehenden Pfeile muss immer&nbsp; $1$&nbsp; sein.&nbsp; Deshalb gilt&nbsp; $q = 1 - p$.  
 
*Aufgrund der Symmetrie des Markovdiagramms sind die ergodischen Wahrscheinlichkeiten alle gleich:
 
*Aufgrund der Symmetrie des Markovdiagramms sind die ergodischen Wahrscheinlichkeiten alle gleich:
 
:$${\rm Pr}(A) ={\rm Pr}(B) ={\rm Pr}(R) = 1/3.$$
 
:$${\rm Pr}(A) ={\rm Pr}(B) ={\rm Pr}(R) = 1/3.$$
  
  
'''(2)'''&nbsp; Wenn man zum Startzeitpunkt $\nu = 0$ im Zustand $B$ ist, ist für den Zeitpunkt $\nu=1$ wegen ${\rm Pr}(B\hspace{0.05cm}|\hspace{0.05cm}B) = 0$ der Zustand $B$ nicht möglich. <br>Man scheitert hier bereits beim Anfangsbuchstaben $B$:  
+
 
 +
'''(2)'''&nbsp; Wenn man zum Startzeitpunkt&nbsp; $\nu = 0$&nbsp; im Zustand&nbsp; $B$&nbsp; ist,&nbsp; ist für den Zeitpunkt&nbsp; $\nu=1$&nbsp; wegen&nbsp; ${\rm Pr}(B\hspace{0.05cm}|\hspace{0.05cm}B) = 0$&nbsp; der Zustand&nbsp; $B$&nbsp; nicht möglich.  
 +
*Man scheitert hier bereits beim Anfangsbuchstaben $B$:  
 
:$$p_{\rm B} \; \underline{ =0}.$$
 
:$$p_{\rm B} \; \underline{ =0}.$$
  
F&uuml;r die Berechnung von $p_{\rm A}$ ist zu beachten: &nbsp; Ausgehend von $A$ geht man im Markovdiagramm zun&auml;chst zu $B$ (mit der Wahrscheinlichkeit $q$), dann f&uuml;nfmal im Uhrzeigersinn (jeweils mit der Wahrscheinlichkeit $p$) und schlie&szlig;lich noch von $R$ nach $A$ (mit der Wahrscheinlichkeit  $q$). Das bedeutet:
+
*F&uuml;r die Berechnung von&nbsp; $p_{\rm A}$&nbsp; ist zu beachten: &nbsp; Ausgehend von&nbsp; $A$&nbsp; geht man im Markovdiagramm zun&auml;chst zu&nbsp; $B$&nbsp; $($mit der Wahrscheinlichkeit $q)$, dann f&uuml;nfmal im Uhrzeigersinn&nbsp; $($jeweils mit der Wahrscheinlichkeit $p)$&nbsp; und schlie&szlig;lich noch von&nbsp; $R$&nbsp; nach&nbsp; $A$&nbsp; $($mit der Wahrscheinlichkeit&nbsp; $q)$.&nbsp; Das bedeutet:
 
:$$p_{\rm A} = q^2 \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 = 3^2 / 4^7 \hspace{0.15cm}\underline {\approx 0.549 \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
 
:$$p_{\rm A} = q^2 \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 = 3^2 / 4^7 \hspace{0.15cm}\underline {\approx 0.549 \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
In &auml;hnlicher Weise erh&auml;lt man:
+
*In &auml;hnlicher Weise erh&auml;lt man:
 
:$$p_{\rm R} = q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^6 = 3 / 4^7 \hspace{0.15cm}\underline {\approx 0.183 \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
 
:$$p_{\rm R} = q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^6 = 3 / 4^7 \hspace{0.15cm}\underline {\approx 0.183 \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
 +
  
  
 
'''(3)'''&nbsp; Durch Mittelung &uuml;ber die bedingten Wahrscheinlichkeiten erh&auml;lt man:
 
'''(3)'''&nbsp; Durch Mittelung &uuml;ber die bedingten Wahrscheinlichkeiten erh&auml;lt man:
:$${\rm Pr}(BARBARA) = p_{\rm A}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(A) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm B}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(B) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm R}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(R).$$
+
:$${\rm Pr}(\rm BARBARA) = p_{\rm A}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(A) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm B}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(B) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm R}  \hspace{0.05cm}\cdot  \hspace{0.05cm} {\rm Pr}(R).$$
 
Dies f&uuml;hrt zum Ergebnis:
 
Dies f&uuml;hrt zum Ergebnis:
:$${\rm Pr}(BARBARA) =  {1}/{3} \cdot \left( q^2 \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5  \hspace{0.1cm} +\hspace{0.1cm}0  \hspace{0.1cm} +\hspace{0.1cm}q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^6  \right)  
+
:$${\rm Pr}(\rm BARBARA) =  {1}/{3} \cdot \left( q^2 \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5  \hspace{0.1cm} +\hspace{0.1cm}0  \hspace{0.1cm} +\hspace{0.1cm}q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^6  \right)  
 
  = \frac{q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 }{3} \cdot (p+q)  
 
  = \frac{q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 }{3} \cdot (p+q)  
 
= \hspace{-0.15cm} \frac{q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 }{3}
 
= \hspace{-0.15cm} \frac{q \hspace{0.05cm}\cdot  \hspace{0.05cm} p^5 }{3}
Zeile 67: Zeile 74:
  
  
'''(4)'''&nbsp; Die im Punkt '''(3)''' berechnete Wahrscheinlichkeit lautet $p^5 \cdot (1-p)/3$, wobei $q= 1-p$ berücksichtigt ist.  
+
'''(4)'''&nbsp; Die im Punkt&nbsp; '''(3)'''&nbsp; berechnete Wahrscheinlichkeit lautet&nbsp; $p^5 \cdot (1-p)/3$,&nbsp; wobei&nbsp; $q= 1-p$&nbsp; berücksichtigt ist.  
  
Durch Nullsetzen des Differentials erh&auml;lt man die Bestimmungsgleichung:
+
*Durch Nullsetzen des Differentials erh&auml;lt man die Bestimmungsgleichung:
 
:$$5 \cdot p^4 - 6 \cdot p^5 = 0 \hspace{0.5cm} \Rightarrow  \hspace{0.5cm}  p_{\rm opt} = 5/6 \hspace{0.15cm}\underline { \approx \rm 0.833}.$$
 
:$$5 \cdot p^4 - 6 \cdot p^5 = 0 \hspace{0.5cm} \Rightarrow  \hspace{0.5cm}  p_{\rm opt} = 5/6 \hspace{0.15cm}\underline { \approx \rm 0.833}.$$
Damit ergibt sich ein gegen&uuml;berder Teilaufgabe '''(3)''' etwa um den Faktor $90$ gr&ouml;&szlig;erer Wert:  
+
*Damit ergibt sich ein gegen&uuml;ber der Teilaufgabe&nbsp; '''(3)'''&nbsp; etwa um den Faktor&nbsp; $90$&nbsp; gr&ouml;&szlig;erer Wert:  
:$${\rm Pr}(BARBARA)  \hspace{0.15cm}\underline { \approx 22  \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
+
:$${\rm Pr}(\rm BARBARA)  \hspace{0.15cm}\underline { \approx 22  \hspace{0.05cm}\cdot  \hspace{0.05cm} 10^{-3}}.$$
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 2. Dezember 2021, 17:28 Uhr

$\rm BARBARA$-Generator

Betrachtet wird hier ein ternärer Zufallsgenerator mit den Symbolen  $A$,  $B$  und  $R$, der durch eine homogene und stationäre Markovkette erster Ordnung beschrieben werden kann.

  • Die Übergangswahrscheinlichkeiten können dem skizzierten Markovdiagramm entnommen werden.
  • Für die ersten drei Teilaufgaben soll stets  $p = 1/4$  gelten.




Hinweis:


Fragebogen

1

Welche der nachfolgenden Aussagen sind zutreffend?

Die Werte von  $p > 0$  und  $q < 1$  sind weitgehend frei wählbar.
Für die Übergangswahrscheinlichkeiten muss gelten:   $p + q = 1$.
Alle Symbole haben gleiche ergodische Wahrscheinlichkeiten.
Es gilt hier:  ${\rm Pr}(A) = 1/2, \; {\rm Pr}(B) = 1/3, \; {\rm Pr}(R) = 1/6$.

2

Wie groß sind die bedingten Wahrscheinlichkeiten  $p_{\rm A}$,  $p_{\rm B}$  und  $p_{\rm C}$,  dass zu den Zeiten zwischen  $ν+1$  und  $ν+7$  die Sequenz  $BARBARA$  ausgegeben wird,
wenn man sich zum Zeitpunkt  $ν$  im Zustand  $A$,  $B$  bzw.  $R$  befindet?  Es gelte  $p = 1/4$.

$p_{\rm A} \ = \ $

$\ \cdot 10^{-3}$
$p_{\rm B} \ = \ $

$\ \cdot 10^{-3}$
$p_{\rm C} \ = \ $

$\ \cdot 10^{-3}$

3

Wie groß ist die Wahrscheinlichkeit insgesamt, dass der Generator zu sieben aufeinanderfolgenden Zeitpunkten die Sequenz  "$\rm BARBARA$"  ausgibt?
Es gelte weiter  $p = 1/4.$

${\rm Pr}(\rm BARBARA)\ = \ $

$\ \cdot 10^{-3}$

4

Wie ist der Parameter  $p_{\rm opt}$  zu wählen, damit  ${\rm Pr}(\rm BARBARA)$  möglichst groß wird?
Welche Wahrscheinlichkeit ergibt sich damit für  "$\rm BARBARA$"?

$p_{\rm opt} \ = \ $

$p = p_{\rm opt}\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(\rm BARBARA)\ = \ $

$\ \cdot 10^{-3}$


Musterlösung

(1)  Richtig sind  der zweite und der dritte Lösungsvorschlag:

  • Die Summe aller abgehenden Pfeile muss immer  $1$  sein.  Deshalb gilt  $q = 1 - p$.
  • Aufgrund der Symmetrie des Markovdiagramms sind die ergodischen Wahrscheinlichkeiten alle gleich:
$${\rm Pr}(A) ={\rm Pr}(B) ={\rm Pr}(R) = 1/3.$$


(2)  Wenn man zum Startzeitpunkt  $\nu = 0$  im Zustand  $B$  ist,  ist für den Zeitpunkt  $\nu=1$  wegen  ${\rm Pr}(B\hspace{0.05cm}|\hspace{0.05cm}B) = 0$  der Zustand  $B$  nicht möglich.

  • Man scheitert hier bereits beim Anfangsbuchstaben $B$:
$$p_{\rm B} \; \underline{ =0}.$$
  • Für die Berechnung von  $p_{\rm A}$  ist zu beachten:   Ausgehend von  $A$  geht man im Markovdiagramm zunächst zu  $B$  $($mit der Wahrscheinlichkeit $q)$, dann fünfmal im Uhrzeigersinn  $($jeweils mit der Wahrscheinlichkeit $p)$  und schließlich noch von  $R$  nach  $A$  $($mit der Wahrscheinlichkeit  $q)$.  Das bedeutet:
$$p_{\rm A} = q^2 \hspace{0.05cm}\cdot \hspace{0.05cm} p^5 = 3^2 / 4^7 \hspace{0.15cm}\underline {\approx 0.549 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-3}}.$$
  • In ähnlicher Weise erhält man:
$$p_{\rm R} = q \hspace{0.05cm}\cdot \hspace{0.05cm} p^6 = 3 / 4^7 \hspace{0.15cm}\underline {\approx 0.183 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-3}}.$$


(3)  Durch Mittelung über die bedingten Wahrscheinlichkeiten erhält man:

$${\rm Pr}(\rm BARBARA) = p_{\rm A} \hspace{0.05cm}\cdot \hspace{0.05cm} {\rm Pr}(A) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm B} \hspace{0.05cm}\cdot \hspace{0.05cm} {\rm Pr}(B) \hspace{0.1cm} + \hspace{0.1cm}p_{\rm R} \hspace{0.05cm}\cdot \hspace{0.05cm} {\rm Pr}(R).$$

Dies führt zum Ergebnis:

$${\rm Pr}(\rm BARBARA) = {1}/{3} \cdot \left( q^2 \hspace{0.05cm}\cdot \hspace{0.05cm} p^5 \hspace{0.1cm} +\hspace{0.1cm}0 \hspace{0.1cm} +\hspace{0.1cm}q \hspace{0.05cm}\cdot \hspace{0.05cm} p^6 \right) = \frac{q \hspace{0.05cm}\cdot \hspace{0.05cm} p^5 }{3} \cdot (p+q) = \hspace{-0.15cm} \frac{q \hspace{0.05cm}\cdot \hspace{0.05cm} p^5 }{3} \hspace{0.15cm}\underline { \approx 0.244 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-3}}.$$


(4)  Die im Punkt  (3)  berechnete Wahrscheinlichkeit lautet  $p^5 \cdot (1-p)/3$,  wobei  $q= 1-p$  berücksichtigt ist.

  • Durch Nullsetzen des Differentials erhält man die Bestimmungsgleichung:
$$5 \cdot p^4 - 6 \cdot p^5 = 0 \hspace{0.5cm} \Rightarrow \hspace{0.5cm} p_{\rm opt} = 5/6 \hspace{0.15cm}\underline { \approx \rm 0.833}.$$
  • Damit ergibt sich ein gegenüber der Teilaufgabe  (3)  etwa um den Faktor  $90$  größerer Wert:
$${\rm Pr}(\rm BARBARA) \hspace{0.15cm}\underline { \approx 22 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-3}}.$$