Difference between revisions of "Aufgaben:Exercise 1.7Z: BARBARA Generator"

Revision as of 17:32, 23 February 2017

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.

Hinweise:

Die Aufgabe gehört zum Kapitel Markovketten.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

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

$p_{\rm A} \ =$

$\ \cdot 10^{-3}$

$p_{\rm B} \ =$

$\ \cdot 10^{-3}$

$p_{\rm C} \ =$

$\ \cdot 10^{-3}$

$p = 1/4\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(BARBARA)\ =$

$\ \cdot 10^{-3}$

$p_{\rm opt} \ =$

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

$\ \cdot 10^{-3}$

Musterlösung

Solution

1. 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.$$

Richtig sind somit der zweite und der dritte Lösungsvorschlag.

2. Wenn man zum Zeitpunkt ν im Zustand B ist, ist für den Zeitpunkt ν + 1 wegen Pr(B|B) = 0 der Zustand B nicht möglich. Man scheitert hier bereits beim Anfangsbuchstaben „B”: p_B = 0

Für die Berechnung von p_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:0.

$$p_{\rm A} = q^2 \hspace{0.05cm}\cdot \hspace{0.05cm} p^5 = 3^2 / 4^7 \hspace{0.15cm}\underline {\approx 5.49 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-4}}.$$

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 1.83 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-4}}.$$

3. Durch Mittelung über die bedingten Wahrscheinlichkeiten erhä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).$$

Dies führt zu dem Ergebnis:

$${\rm Pr}(BARBARA) \hspace{-0.15cm} = \hspace{-0.15cm} \frac {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 2.44 \hspace{0.05cm}\cdot \hspace{0.05cm} 10^{-4}}.$$

4. Die im Punkt c) berechnete Wahrscheinlichkeit lautet p⁵ · (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 = 5/6 \hspace{0.15cm}\underline { \approx \rm 0.833}.$$

Damit ergibt sich ein gegenüber c) etwa um den Faktor 90 größerer Wert: Pr(BARBARA) ≈ 0.022.

@@ Line 2: / Line 2: @@
 {{quiz-Header|Buchseite=Stochastische Signaltheorie/Markovketten}}
-[[File:P_ID454__Sto_Z_1_7.png|right|]]
+[[File:P_ID454__Sto_Z_1_7.png|right|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 Teilaufgaben a) bis c) 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.
+''Hinweise:''
+*Die Aufgabe gehört zum  Kapitel [[Stochastische_Signaltheorie/Markovketten|Markovketten]].
+*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
-'''Hinweis''': Diese Aufgabe bezieht sich auf das Kapitel 1.4.
 ===Fragebogen===
@@ Line 16: / Line 18: @@
 |type="[]"}
 - Die Werte von $p > 0$ und $q < 1$ sind weitgehend frei wählbar.
-+ Für die Übergangswahrscheinlichkeiten muss gelten: $p + q = 1$.
++ Für die Übergangswahrscheinlichkeiten muss gelten: &nbsp; $p + q = 1$.
 + Alle Symbole haben gleiche ergodische Wahrscheinlichkeiten.
-- Es gilt hier: $Pr(A) = 1/2, Pr(B) = 1/3, Pr(R) = 1/6$.
+- Es gilt hier: ${\rm Pr}(A) = 1/2, \; {\rm Pr}(B) = 1/3, \; {\rm Pr}(R) = 1/6$.
-{Wie groß sind die bedingten Wahrscheinlichkeiten $p_A$, $p_B$ und $p_R$, dass zu den Zeiten $ν+1, ... , ν+7$ „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 $p_{\rm A}$, $p_{\rm B}$ und $p_{\rm C}$, dass im Zeitbereich zwischen $ν+1$ und $ν+7$ $\rm die Sequenz $BARBARA$ ausgegeben wird, wenn man sich zum Zeitpunkt $ν$ im Zustand $A$, $B$ bzw. $R$ befindet? Es gelte $p = 1/4$.
 |type="{}"}
-$p_A$ = { 5.49 3% } $* 10^{}$ ^ { -4 }
+$p_{\rm A} \ =$  { 0.549 3% } $\ \cdot 10^{-3}$
-$p_B$ = { 0 3% }
+$p_{\rm B} \ =$ { 0. } $\ \cdot 10^{-3}$
-$p_R$ = { 1.83 3% } $* 10^{}$ ^ { -4 }
+$p_{\rm C} \ =$ { 0.183 3% } $\ \cdot 10^{-3}$
-{Wie groß ist die Wahrscheinlichkeit insgesamt, dass der Generator zu sieben aufeinanderfolgenden Zeitpunkten BARBARA ausgibt $(p = 1/4)$?
+{Wie groß ist die Wahrscheinlichkeit insgesamt, dass der Generator zu sieben aufeinanderfolgenden Zeitpunkten die Sequenz $BARBARA$ ausgibt.  Es gelte weiter $(p = 1/4)$?
 |type="{}"}
-$Pr(BARBARA)$ = { 2.44 3% } $* 10^{}$ ^ { -4 }
+$p = 1/4\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(BARBARA)\ =$ { 0.244 3% } $\ \cdot 10^{-3}$
-{Wie ist der Parameter $p$ zu wählen, damit $Pr(BARBARA)$ möglichst groß wird? Welche Wahrscheinlichkeit ergibt sich damit für BARBARA?
+{Wie ist der Parameter $p_{\rm opt}$ zu wählen, damit $Pr(BARBARA)$ möglichst groß wird? Welche Wahrscheinlichkeit ergibt sich damit für BARBARA?
 |type="{}"}
-$p$ = { 0.8333 3% }
+$p_{\rm opt} \ =$  { 0.8333 3% }
-$Pr(BARBARA)$ = { 0.022 3% }
+$p = p_{\rm opt}\hspace{-0.1cm}: \hspace{0.3cm}{\rm Pr}(BARBARA)$ = { 22 3% } $\ \cdot 10^{-3}$
 </quiz>