*The exercise belongs to the chapter [[Information_Theory/Discrete_Sources_with_Memory|Discrete Sources with Memory]].
*Reference is made in particular to the page [[Information_Theory/Discrete_Sources_with_Memory#Non-binary_Markov_sources|Non-binary Markov sources]].
*For all entropies, add the pseudo-unit "bit/symbol".
''Hinweise:''
*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
*Bezug genommen wird insbesondere auf die Seite [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]].
*Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen.
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Für welche Parameter $p$ und $q$ ergibt sich die maximale Entropie pro Symbol?
{For which parameters $p$ and $q$ does the maximum entropy per symbol result?
{Es sei $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung?
{Let $p = 1/4$ and $q = 1$. What is the value of the first entropy approximation in this case?
|type="{}"}
|type="{}"}
$H_1 = \ \ $ { 1.585 3% } $\ \rm bit/Symbol$
$H_1 = \ \ $ { 1.585 3% } $\ \rm bit/symbol$
{Weiterhin gelte $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung?
{Furthermore, let $p = 1/4$ and $q = 1$. What value results in this case for the second entropy approximation?
|type="{}"}
|type="{}"}
$H_2 = \ \ $ { 1.5425 1% } $\ \rm bit/Symbol$
$H_2 = \ \ $ { 1.5425 1% } $\ \rm bit/symbol$
{Wie groß ist die tatsächliche Quellenentropie mit $p = 1/4$ und $q = 1$?
{What is the actual source entropy $H= H_{k \to \infty}$ with $p = 1/4$ and $q = 1$?
|type="{}"}
|type="{}"}
$H = \ \ $ { 1.5 1% } $\ \rm bit/Symbol$
$H = \ \ $ { 1.5 1% } $\ \rm bit/symbol$
{Wie groß ist die tatsächliche Quellenentropie mit $p = 1/2$ und $q = 0$?
{What is the actual source entropy $H= H_{k \to \infty}$ with $p = 1/2$ and $q = 0$?
|type="{}"}
|type="{}"}
$H = \ \ $ { 0.667 1% } $\ \rm bit/Symbol$
$H = \ \ $ { 0.667 1% } $\ \rm bit/symbol$
Line 66:
Line 63:
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)''' Die maximale Entropie ergibt sich dann, wenn die Symbole $\rm A$, $\rm B$ und $\rm C$ gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:
'''(1)''' The maximum entropy results when the symbols $\rm A$, $\rm B$ and $\rm C$ are equally probable and the symbols within the sequence are statistically independent of each other. Then the following must apply:
[[File:Inf_Z_1_6_vers2.png|right|frame|Übergangsdiagramm für $p = 1/4$, $q = 1$]]
From this, the values we are looking for can be determined:
*Beispielsweise erhält man aus $p_{\rm C|C} = 1/3$ den Wert $p \hspace{0.15cm}\underline{= 1/3}$.
*For example, from $p_{\rm C|C} = 1/3$ one obtains the value $p \hspace{0.15cm}\underline{= 1/3}$.
*Berücksichtigt man noch die Beziehung $p_{\rm A|A} = p \cdot q$, so folgt $q \hspace{0.15cm}\underline{= 1}$.
*If one also takes into account the relationship $p_{\rm A|A} = p \cdot q$, then $q \hspace{0.15cm}\underline{= 1}$.
* Damit ergibt sich die maximale Entropie $H_\text{max} ={\rm log_2} \ 3\hspace{0.15cm}\underline{= 1.585\ \rm bit/Symbol}$.
*This gives the maximum entropy $H_\text{max} ={\rm log_2} \ 3\hspace{0.15cm}\underline{= 1.585\ \rm bit/symbol}$.
'''(2)''' Mit den Parameterwerten Übergangsdiagramm für $p = 1/4$ und $q = 1$ ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:
'''(2)''' With the parameter values $p = 1/4$ and $q = 1$ , we obtain the adjacent transition diagram, which has the following symmetries:
[[File:Inf_Z_1_6e_vers2.png|right|frame|Übergangsdiagramm für $p = 1/4$, $q = 0$]]
'''(3)''' For the second entropy approximation one needs $3^2 = 9$ joint probabilities.
'''(5)''' Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität $p_{\rm B} = 0$ gelten wird, da $\rm B$ höchstens zum Starzeitpunkt einmal auftreten kann.
*Using the result from '''(2)''' , one obtains for this:
*Es liegt also eine binäre Markovkette mit den Symbolen $\rm A$ und $\rm C$ vor.
'''(5)''' From the adjacent transition diagram with the current parameters, one can see that in the case of stationarity $p_{\rm B} = 0$ will apply, since $\rm B$ can occur at most once at the starting time.
*So there is a binary Markov chain with the symbols $\rm A$ and $\rm C$ .
(1) The maximum entropy results when the symbols $\rm A$, $\rm B$ and $\rm C$ are equally probable and the symbols within the sequence are statistically independent of each other. Then the following must apply:
Transition diagram for $p = 1/4$, $q = 1$
(5) From the adjacent transition diagram with the current parameters, one can see that in the case of stationarity $p_{\rm B} = 0$ will apply, since $\rm B$ can occur at most once at the starting time.
So there is a binary Markov chain with the symbols $\rm A$ and $\rm C$ .
