Difference between revisions of "Aufgaben:Exercise 1.1Z: Binary Entropy Function"

From LNTwww
m (Text replacement - "optimisation" to "optimization")
 
(19 intermediate revisions by 4 users not shown)
Line 1: Line 1:
  
{{quiz-Header|Buchseite=Informationstheorie/Gedächtnislose Nachrichtenquellen
+
{{quiz-Header|Buchseite=Information_Theory/Discrete_Memoryless_Sources
 
}}
 
}}
  
[[File:P_ID2234__Inf_Z_1_1.png|right|Inf_Z_1_1_vers2.png]]
+
[[File:P_ID2234__Inf_Z_1_1.png|right|frame|Binary entropy function <br>in "bits" und "nats"]]
Wir betrachten eine Folge von binären Zufallsgrößen mit dem Symbolvorrat $\{ \rm A, \ B \}$ &nbsp; &rArr; &nbsp; $M = 2$. Die Auftrittswahrscheinlichkeiten der beiden Symbole seien $p_{\rm A }= p$ und $p_{\rm B } = 1 - p$.
+
We consider a sequence of binary random variables with the symbol set&nbsp; $\{ \rm A, \ B \}$ &nbsp; &rArr; &nbsp; $M = 2$.&nbsp; Let the probabilities of occurrence of the two symbols be&nbsp; $p_{\rm A }= p$ &nbsp;and&nbsp; $p_{\rm B } = 1 - p$.
  
Die einzelnen Folgenelemente sind statistisch unabhängig. Für die Entropie dieser Nachrichtenquelle gilt gleichermaßen:
+
The individual sequence elements are statistically independent.&nbsp; The entropy of this message source is equally valid:
:$$H_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ld}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ld}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} [bit]}\hspace{0.05cm},$$
+
:$$H_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ld}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ld}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} \big [bit \big  ]}\hspace{0.05cm},$$
:$$ H'_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} [nat]}\hspace{0.05cm}.$$
+
:$$ H'_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} \big [nat\big ]}\hspace{0.05cm}.$$
In diesen Gleichungen werden als Kurzbezeichnungen verwendet:
+
In these equations, the shorthand terms used are:
  
* der <i>natürliche</i> Logarithmus &nbsp; &rArr; &nbsp; $ \ln \hspace{0.05cm} p = \log_{\rm e} \hspace{0.05cm} p$,
+
* the&nbsp; "natural"&nbsp; logarithm &nbsp; &rArr; &nbsp; $ {\ln} \hspace{0.09cm} p = \log_{\rm e} \hspace{0.05cm} p$,
* der Logarithmus <i>dualis</i> &nbsp; &rArr; &nbsp; ${\rm ld} \hspace{0.05cm} p = \log_2 \hspace{0.05cm} p$.
+
* the&nbsp; "binary"&nbsp; logarithm &nbsp; &rArr; &nbsp; ${\rm ld} \hspace{0.09cm} p = \log_2 \hspace{0.05cm} p$.
  
  
Die Grafik zeigt diese binäre Entropiefunktion in Abhängigkeit des Parameters $p$, wobei $0 ≤ p ≤ 1$ vorausgesetzt wird.
+
The plot shows the binary entropy function as a function of the parameter&nbsp; $p$, assuming&nbsp; $0 ≤ p ≤ 1$&nbsp;.
  
In den Teilaufgaben (5) und (6) soll der relative Fehler ermittelt werden, wenn die Symbolwahrscheinlichkeit $p$ per Simulation (also als relative Häufigkeit $h$) ermittelt wurde und sich dabei fälschlicherweise $h = 0.9 \cdot p$ ergeben hat. Der relative Fehler ist dann wie folgt gegeben:
+
In subtasks&nbsp; '''(5)'''&nbsp; and&nbsp; '''(6)'''&nbsp; the relative error is to be determined if the symbol probability &nbsp;$p$&nbsp; was determined by simulation&nbsp; $($i.e., as a relative frequency&nbsp; $h)$,&nbsp; resulting in &nbsp;$h = 0.9 \cdot p$&nbsp; by mistake.&nbsp; The relative error is then given as follows:
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(h)- H_{\rm bin}(p)}{H_{\rm bin}(p)}\hspace{0.05cm}.$$
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(h)- H_{\rm bin}(p)}{H_{\rm bin}(p)}\hspace{0.05cm}.$$
  
  
''Hinweise:''
 
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Gedächtnislose_Nachrichtenquellen|Gedächtnislose Nachrichtenquellen]].
 
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 
  
  
===Fragebogen===
+
 
 +
 
 +
''Hint:''
 +
*The task belongs to the chapter&nbsp; [[Information_Theory/Gedächtnislose_Nachrichtenquellen|Discrete Memoryless Sources]].
 +
 +
 
 +
 
 +
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wie hängen $H_{\rm bin}(p)$ in bit und $H'_{\rm bin}(p)$ in nat zusammen?
+
{How are&nbsp; $H_{\rm bin}(p)$&nbsp; related to the unit "bit" and&nbsp; $H'_{\rm bin}(p)$&nbsp; related to the unit "nat"?
 
|type="[]"}
 
|type="[]"}
+ $H_{\rm bin}(p)$ und $H'_{\rm bin}(p)$ unterscheiden sich um einen Faktor.
+
+ $H_{\rm bin}(p)$&nbsp; and&nbsp; $H'_{\rm bin}(p)$&nbsp; differ by a factor.
- Es gilt $H'_{\rm bin}(p) = H_{\rm bin}(\ln \ p)$.
+
- It holds that&nbsp; $H'_{\rm bin}(p) = H_{\rm bin}(\ln \ p)$.
- Es gilt $H'_{\rm bin}(p) = 1 + H_{\rm bin}(2 p)$.
+
- It holds that&nbsp; $H'_{\rm bin}(p) = 1 + H_{\rm bin}(2 p)$.
  
  
{Zeigen Sie, dass sich das Maximum der binären Entropiefunktion für $p = 0.5$ ergibt. Wie groß ist $H_\text{bin}(p = 0.5)$?
+
{Show that the maximum of the binary entropy function is obtained for&nbsp; $p = 0.5$&nbsp;.&nbsp; What is&nbsp; $H_\text{bin}(p = 0.5)$?
 
|type="{}"}
 
|type="{}"}
$H_\text{bin}(p = 0.5) \ = $  { 1 } $\ \rm bit$
+
$H_\text{bin}(p = 0.5) \ = \ $  { 1 } $\ \rm bit$
  
  
{Berechnen Sie den binären Entropiewert für $p = 0.05$.
+
{Calculate the binary entropy value for&nbsp; $p = 0.05$.
 
|type="{}"}
 
|type="{}"}
$H_\text{bin}(p = 0.05) \ = $ { 0.286 3% } $\ \rm bit$
+
$H_\text{bin}(p = 0.05) \ = \ $ { 0.286 3% } $\ \rm bit$
  
  
{Geben Sie den größeren der beiden $p$&ndash;Werte ein, die sich aus der Gleichung $H_\text{bin}(p)= 0.5 \ \rm bit$ ergeben.
+
{Enter the larger of the two&nbsp; $p$&ndash;values given by the equation &nbsp; $H_\text{bin}(p)= 0.5 \ \rm bit$&nbsp;.
 
|type="{}"}
 
|type="{}"}
$p \ = $ { 0.89 3% }
+
$p \ = \ $ { 0.89 3% }
  
  
{Durch unzureichende Simulation wurde $p = 0.5$ um $10\%$ zu niedrig ermittelt. Wie groß ist der prozentuale Fehler hinsichtlich der Entropie?
+
{Due to insufficient simulation,&nbsp; $p = 0.5$&nbsp; was determined&nbsp; $10\%$ too low.&nbsp; What is the percentage error with respect to the entropy?
 
|type="{}"}
 
|type="{}"}
$p = 0.45\ {\rm statt}\ p=0.5\hspace{-0.1cm}:\ \ \varepsilon_H \ = $ { -0.72--0.68 } $\ \rm \%$
+
$p = 0.45\ \ {\rm instead of}\ \ p=0.5\hspace{-0.1cm}:\ \ \varepsilon_H \ = \ $ { -0.72--0.68 } $\ \rm \%$
  
  
{Durch unzureichende Simulation wurde $p = 0.05$ um $10\%$ zu niedrig ermittelt. Wie groß ist der prozentuale Fehler hinsichtlich der Entropie?
+
{Due to insufficient simulation,&nbsp; $p = 0.05$&nbsp; was determined&nbsp; $10\%$&nbsp; too low.&nbsp; What is the percentage error with respect to the entropy here?
 
|type="{}"}
 
|type="{}"}
$p = 0.045\ {\rm statt}\ p=0.05\hspace{-0.1cm}:\ \ \varepsilon_H \ = $ { -7.44--7.16 } $\ \rm \%$
+
$p = 0.045\ \ {\rm statt}\ \ p=0.05\hspace{-0.1cm}:\ \ \varepsilon_H \ = \ $ { -7.44--7.16 } $\ \rm \%$
  
  
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<i>Hinweis:</i> Aus Platzgründen verwenden wir in dieser Musterlösung &bdquo;ld&rdquo; anstelle von  &bdquo;log<sub>2</sub>&rdquo;.
+
'''(1)'''&nbsp; The <u>first suggested solution</u> is correct. The other two specifications do not make sense.
 
+
*The entropy function&nbsp; $H'_{\rm bin}(p)$&nbsp; is according to the specification:
'''(1)'''&nbsp; Richtig ist der <u>erste Lösungsvorschlag</u>. Die beiden weiteren Vorgaben machen keinen Sinn.
+
:$$H'_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p} = {\rm ln}\hspace{0.1cm}2 \cdot \left [ p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p}\right ]$$
*Die Entropiefunktion $H'_{\rm bin}(p)$ lautet entsprechend der Angabe:
 
:$$H'_{\rm bin}(p) \hspace{0.1cm}  =  \hspace{0.1cm}  p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p} = {\rm ln}\hspace{0.1cm}2 \cdot \left [ p \cdot {\rm ld}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ld}\hspace{0.1cm}\frac{1}{1-p}\right ]$$
 
 
:$$\Rightarrow \hspace{0.3cm} H'_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} nat)}=
 
:$$\Rightarrow \hspace{0.3cm} H'_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} nat)}=
 
  {\rm ln}\hspace{0.1cm}2 \cdot H_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} bit)} = 0.693\cdot H_{\rm bin}(p)\hspace{0.05cm}.$$
 
  {\rm ln}\hspace{0.1cm}2 \cdot H_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} bit)} = 0.693\cdot H_{\rm bin}(p)\hspace{0.05cm}.$$
  
'''(2)'''&nbsp; Die Optimierungsbedingung lautet ${\rm d}H_{\rm bin}(p)/{\rm d}p = 0$ bzw.
+
 
 +
 
 +
'''(2)'''&nbsp; The optimization condition is&nbsp; ${\rm d}H_{\rm bin}(p)/{\rm d}p = 0$&nbsp; resp.
 
:$$\frac{{\rm d}H'_{\rm bin}(p)}{{\rm d}p} \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \frac{\rm d}{{\rm d}p}
 
:$$\frac{{\rm d}H'_{\rm bin}(p)}{{\rm d}p} \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \frac{\rm d}{{\rm d}p}
   \left [ - p \cdot {\rm ln}\hspace{0.1cm}p - (1-p) \cdot {\rm ln}\hspace{0.1cm}({1-p})\right ] \stackrel{!}{=} 0$$
+
   \big [ - p \cdot {\rm ln}\hspace{0.1cm}p - (1-p) \cdot {\rm ln}\hspace{0.1cm}({1-p})\big ] \stackrel{!}{=} 0$$
 
:$$\Rightarrow \hspace{0.3cm}  
 
:$$\Rightarrow \hspace{0.3cm}  
 
  - {\rm ln}\hspace{0.1cm}p - p \cdot \frac {1}{p}+ {\rm ln}\hspace{0.1cm}(1-p) + (1-p)\cdot \frac {1}{1- p}\stackrel{!}{=} 0$$
 
  - {\rm ln}\hspace{0.1cm}p - p \cdot \frac {1}{p}+ {\rm ln}\hspace{0.1cm}(1-p) + (1-p)\cdot \frac {1}{1- p}\stackrel{!}{=} 0$$
 
:$$\Rightarrow \hspace{0.3cm} {\rm ln}\hspace{0.1cm}\frac {1-p}{p}= 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\frac {1-p}{p}= 1
 
:$$\Rightarrow \hspace{0.3cm} {\rm ln}\hspace{0.1cm}\frac {1-p}{p}= 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\frac {1-p}{p}= 1
 
  \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline { p = 0.5}\hspace{0.05cm}.$$
 
  \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline { p = 0.5}\hspace{0.05cm}.$$
Die Entropiewerte für $p = 0.5$ lauten somit:
+
*The entropy values for&nbsp; $p = 0.5$&nbsp; are thus:
 
:$$H'_{\rm bin}(p = 0.5) \hspace{0.1cm}  =  \hspace{0.1cm}  -2 \cdot 0.5 \cdot {\rm ln}\hspace{0.1cm}0.5 = {\rm ln}\hspace{0.1cm}2 = 0.693 \, {\rm nat}\hspace{0.05cm},$$
 
:$$H'_{\rm bin}(p = 0.5) \hspace{0.1cm}  =  \hspace{0.1cm}  -2 \cdot 0.5 \cdot {\rm ln}\hspace{0.1cm}0.5 = {\rm ln}\hspace{0.1cm}2 = 0.693 \, {\rm nat}\hspace{0.05cm},$$
:$$  H_{\rm bin}(p = 0.5) \hspace{0.1cm}  =  \hspace{0.1cm}  -2 \cdot 0.5 \cdot {\rm ld}\hspace{0.1cm}0.5 = {\rm ld}\hspace{0.1cm}2 \hspace{0.15cm}\underline {= 1 \, {\rm bit}}\hspace{0.05cm}.$$
+
:$$  H_{\rm bin}(p = 0.5) \hspace{0.1cm}  =  \hspace{0.1cm}  -2 \cdot 0.5 \cdot {\rm ld}\hspace{0.1cm}0.5 = {\rm log_2}\hspace{0.1cm}2 \hspace{0.15cm}\underline {= 1 \, {\rm bit}}\hspace{0.05cm}.$$
 +
 
  
'''(3)'''&nbsp; Für $p = 5\%$ erhält man:
+
 
:$$H_{\rm bin}(p = 0.05) \hspace{0.1cm}  =  \hspace{0.1cm}  0.05 \cdot {\rm ld}\hspace{0.1cm}\frac{1}{0.05}+ 0.95 \cdot {\rm ld}\hspace{0.1cm}\frac{1}{0.95}=  \frac{1}{0.693} \cdot \left [ 0.05 \cdot {\rm ln}\hspace{0.1cm}20+ 0.95 \cdot {\rm ln}\hspace{0.1cm}1.053\right ]
+
'''(3)'''&nbsp; For&nbsp; $p = 5\%$&nbsp; we get:
 +
:$$H_{\rm bin}(p = 0.05) \hspace{0.1cm}  =  \hspace{0.1cm}  0.05 \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{0.05}+ 0.95 \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{0.95}=  \frac{1}{0.693} \cdot \big [ 0.05 \cdot {\rm ln}\hspace{0.1cm}20+ 0.95 \cdot {\rm ln}\hspace{0.1cm}1.053\big ]
 
  \hspace{0.15cm}\underline {\approx 0.286 \, {\rm bit}}\hspace{0.05cm}.$$
 
  \hspace{0.15cm}\underline {\approx 0.286 \, {\rm bit}}\hspace{0.05cm}.$$
  
'''(4)'''&nbsp; Diese Teilaufgabe lässt sich nicht in geschlossener Form lösen, sondern durch &bdquo;Probieren&rdquo;. Eine Lösung liefert das Ergebnis:
+
 
 +
 
 +
'''(4)'''&nbsp; This sub-task cannot be solved in closed form, but by "trial and error".  
 +
*A solution gives the result:
 
:$$H_{\rm bin}(p = 0.10) = 0.469 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm}H_{\rm bin}(p = 0.12) = 0.529 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm}
 
:$$H_{\rm bin}(p = 0.10) = 0.469 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm}H_{\rm bin}(p = 0.12) = 0.529 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm}
 
  H_{\rm bin}(p = 0.11) \approx 0.5 \, {\rm bit} \hspace{0.3cm}
 
  H_{\rm bin}(p = 0.11) \approx 0.5 \, {\rm bit} \hspace{0.3cm}
 
\Rightarrow \hspace{0.3cm}p_1 \approx 0.11\hspace{0.05cm}. $$
 
\Rightarrow \hspace{0.3cm}p_1 \approx 0.11\hspace{0.05cm}. $$
Die zweite (gesuchte) Lösung ergibt sich aus der Symmetrie von $H_{\rm bin}(p)$ zu $p_2 = 1 -p_1 \hspace{0.15cm}\underline{= 0.89}$.
+
*The second solution results from the symmetry of &nbsp; $H_{\rm bin}(p)$&nbsp; to &nbsp;$p_2 = 1 -p_1 \hspace{0.15cm}\underline{= 0.89}$.
 +
 
 +
 
 +
 
  
'''(5)'''&nbsp; Mit $p = 0.45$ erhält man $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm  bit$. Der relative Fehler bezüglich Entropie ist somit
+
'''(5)'''&nbsp; With&nbsp; $p = 0.45$&nbsp; one obtains&nbsp; $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm  bit$.&nbsp; The relative error with respect to entropy is thus
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.45)- H_{\rm bin}(p= 0.5)}{H_{\rm bin}(p = 0.5)}= \frac{0.993- 1}{1}\hspace{0.15cm}\underline {= -0.7 \, {\rm \%}}
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.45)- H_{\rm bin}(p= 0.5)}{H_{\rm bin}(p = 0.5)}= \frac{0.993- 1}{1}\hspace{0.15cm}\underline {= -0.7 \, {\rm \%}}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Das Minuszeichen deutet darauf hin, dass der Entropiewert $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm  bit$ zu klein ist. Hätte die Simulation den zu großen Wert $p = 0.55$ ergeben, so wäre die Entropie und auch der relative Fehler genau so groß.
+
*The minus sign indicates that the entropy value&nbsp; $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm  bit$&nbsp; is too small.
 +
*If the simulation had yielded the too large value&nbsp; $p = 0.55$&nbsp;, the entropy and also the relative error would be just as large.
 +
 
 +
 
 +
 
  
'''(6)'''&nbsp; Es gilt $H_{\rm bin}(p = 0.045) = 0.265\hspace{0.05cm}\rm  bit$. Mit dem Ergebnis der Teilaufgabe (3) &nbsp; &#8658; &nbsp; $H_{\rm bin}(p = 0.05) = 0.286\hspace{0.05cm}\rm  bit$folgt daraus für den relativen Fehler bezüglich der Entropie:
+
'''(6)'''&nbsp; &nbsp; $H_{\rm bin}(p = 0.045) = 0.265\hspace{0.05cm}\rm  bit$ is valid.
 +
*With the result of subtask&nbsp; '''(3)''' &nbsp; &#8658; &nbsp; $H_{\rm bin}(p = 0.05) = 0.286\hspace{0.05cm}\rm  bit$&nbsp; it follows for the relative error with respect to the entropy:
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.045)- H_{\rm bin}(p= 0.05)}{H_{\rm bin}(p = 0.05)}= \frac{0.265- 0.286}{0.286}\hspace{0.15cm}\underline {= -7.3 \, {\rm \%}}
 
:$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.045)- H_{\rm bin}(p= 0.05)}{H_{\rm bin}(p = 0.05)}= \frac{0.265- 0.286}{0.286}\hspace{0.15cm}\underline {= -7.3 \, {\rm \%}}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Das Ergebnis zeigt:  
+
*The result shows:
*Eine falsche Bestimmung der Symbolwahrscheinlichkeiten um $10\%$ macht sich für $p = 0.05$ aufgrund des steileren $H_{\rm bin}(p)$&ndash;Verlaufs deutlich stärker bemerkbar als für $p = 0.5$.  
+
#&nbsp;An incorrect determination of the symbol probabilities by&nbsp; $10\%$&nbsp; is much more noticeable for&nbsp; $p = 0.05$&nbsp; due to the steeper&nbsp; $H_{\rm bin}(p)$ course than for&nbsp; $p = 0.5$.  
*Eine zu große Wahrscheinlichkeit $p = 0.055$ hätte zu $H_{\rm bin}(p = 0.055) = 0.307\hspace{0.05cm}\rm  bit$ geführt und damit zu einer Verfälschung um $\varepsilon_H = +7.3\%$. In diesem Bereich verläuft die Entropiekurve also (mit guter Näherung) linear.
+
#&nbsp;A too large probability&nbsp; $p = 0.055$&nbsp; would have led to&nbsp; $H_{\rm bin}(p = 0.055) = 0.307\hspace{0.05cm}\rm  bit$&nbsp; and thus to a distortion of&nbsp; $\varepsilon_H = +7.3\%$.&nbsp;
 +
#In this range, the entropy curve is thus linear (with a good approximation).
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie|^1.1 Gedächtnislose Nachrichtenquellen^]]
+
[[Category:Information Theory: Exercises|^1.1 Memoryless Sources^]]

Latest revision as of 13:50, 21 September 2021

Binary entropy function
in "bits" und "nats"

We consider a sequence of binary random variables with the symbol set  $\{ \rm A, \ B \}$   ⇒   $M = 2$.  Let the probabilities of occurrence of the two symbols be  $p_{\rm A }= p$  and  $p_{\rm B } = 1 - p$.

The individual sequence elements are statistically independent.  The entropy of this message source is equally valid:

$$H_{\rm bin}(p) \hspace{0.1cm} = \hspace{0.1cm} p \cdot {\rm ld}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ld}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} \big [bit \big ]}\hspace{0.05cm},$$
$$ H'_{\rm bin}(p) \hspace{0.1cm} = \hspace{0.1cm} p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p}\hspace{0.15cm}{\rm in \hspace{0.15cm} \big [nat\big ]}\hspace{0.05cm}.$$

In these equations, the shorthand terms used are:

  • the  "natural"  logarithm   ⇒   $ {\ln} \hspace{0.09cm} p = \log_{\rm e} \hspace{0.05cm} p$,
  • the  "binary"  logarithm   ⇒   ${\rm ld} \hspace{0.09cm} p = \log_2 \hspace{0.05cm} p$.


The plot shows the binary entropy function as a function of the parameter  $p$, assuming  $0 ≤ p ≤ 1$ .

In subtasks  (5)  and  (6)  the relative error is to be determined if the symbol probability  $p$  was determined by simulation  $($i.e., as a relative frequency  $h)$,  resulting in  $h = 0.9 \cdot p$  by mistake.  The relative error is then given as follows:

$$\varepsilon_{H} = \frac{H_{\rm bin}(h)- H_{\rm bin}(p)}{H_{\rm bin}(p)}\hspace{0.05cm}.$$




Hint:


Questions

1

How are  $H_{\rm bin}(p)$  related to the unit "bit" and  $H'_{\rm bin}(p)$  related to the unit "nat"?

$H_{\rm bin}(p)$  and  $H'_{\rm bin}(p)$  differ by a factor.
It holds that  $H'_{\rm bin}(p) = H_{\rm bin}(\ln \ p)$.
It holds that  $H'_{\rm bin}(p) = 1 + H_{\rm bin}(2 p)$.

2

Show that the maximum of the binary entropy function is obtained for  $p = 0.5$ .  What is  $H_\text{bin}(p = 0.5)$?

$H_\text{bin}(p = 0.5) \ = \ $

$\ \rm bit$

3

Calculate the binary entropy value for  $p = 0.05$.

$H_\text{bin}(p = 0.05) \ = \ $

$\ \rm bit$

4

Enter the larger of the two  $p$–values given by the equation   $H_\text{bin}(p)= 0.5 \ \rm bit$ .

$p \ = \ $

5

Due to insufficient simulation,  $p = 0.5$  was determined  $10\%$ too low.  What is the percentage error with respect to the entropy?

$p = 0.45\ \ {\rm instead of}\ \ p=0.5\hspace{-0.1cm}:\ \ \varepsilon_H \ = \ $

$\ \rm \%$

6

Due to insufficient simulation,  $p = 0.05$  was determined  $10\%$  too low.  What is the percentage error with respect to the entropy here?

$p = 0.045\ \ {\rm statt}\ \ p=0.05\hspace{-0.1cm}:\ \ \varepsilon_H \ = \ $

$\ \rm \%$


Solution

(1)  The first suggested solution is correct. The other two specifications do not make sense.

  • The entropy function  $H'_{\rm bin}(p)$  is according to the specification:
$$H'_{\rm bin}(p) \hspace{0.1cm} = \hspace{0.1cm} p \cdot {\rm ln}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm ln}\hspace{0.1cm}\frac{1}{1-p} = {\rm ln}\hspace{0.1cm}2 \cdot \left [ p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p}\right ]$$
$$\Rightarrow \hspace{0.3cm} H'_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} nat)}= {\rm ln}\hspace{0.1cm}2 \cdot H_{\rm bin}(p) \hspace{0.15cm}{\rm (in \hspace{0.15cm} bit)} = 0.693\cdot H_{\rm bin}(p)\hspace{0.05cm}.$$


(2)  The optimization condition is  ${\rm d}H_{\rm bin}(p)/{\rm d}p = 0$  resp.

$$\frac{{\rm d}H'_{\rm bin}(p)}{{\rm d}p} \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \frac{\rm d}{{\rm d}p} \big [ - p \cdot {\rm ln}\hspace{0.1cm}p - (1-p) \cdot {\rm ln}\hspace{0.1cm}({1-p})\big ] \stackrel{!}{=} 0$$
$$\Rightarrow \hspace{0.3cm} - {\rm ln}\hspace{0.1cm}p - p \cdot \frac {1}{p}+ {\rm ln}\hspace{0.1cm}(1-p) + (1-p)\cdot \frac {1}{1- p}\stackrel{!}{=} 0$$
$$\Rightarrow \hspace{0.3cm} {\rm ln}\hspace{0.1cm}\frac {1-p}{p}= 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\frac {1-p}{p}= 1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline { p = 0.5}\hspace{0.05cm}.$$
  • The entropy values for  $p = 0.5$  are thus:
$$H'_{\rm bin}(p = 0.5) \hspace{0.1cm} = \hspace{0.1cm} -2 \cdot 0.5 \cdot {\rm ln}\hspace{0.1cm}0.5 = {\rm ln}\hspace{0.1cm}2 = 0.693 \, {\rm nat}\hspace{0.05cm},$$
$$ H_{\rm bin}(p = 0.5) \hspace{0.1cm} = \hspace{0.1cm} -2 \cdot 0.5 \cdot {\rm ld}\hspace{0.1cm}0.5 = {\rm log_2}\hspace{0.1cm}2 \hspace{0.15cm}\underline {= 1 \, {\rm bit}}\hspace{0.05cm}.$$


(3)  For  $p = 5\%$  we get:

$$H_{\rm bin}(p = 0.05) \hspace{0.1cm} = \hspace{0.1cm} 0.05 \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{0.05}+ 0.95 \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{0.95}= \frac{1}{0.693} \cdot \big [ 0.05 \cdot {\rm ln}\hspace{0.1cm}20+ 0.95 \cdot {\rm ln}\hspace{0.1cm}1.053\big ] \hspace{0.15cm}\underline {\approx 0.286 \, {\rm bit}}\hspace{0.05cm}.$$


(4)  This sub-task cannot be solved in closed form, but by "trial and error".

  • A solution gives the result:
$$H_{\rm bin}(p = 0.10) = 0.469 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm}H_{\rm bin}(p = 0.12) = 0.529 \, {\rm bit}\hspace{0.05cm},\hspace{0.2cm} H_{\rm bin}(p = 0.11) \approx 0.5 \, {\rm bit} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}p_1 \approx 0.11\hspace{0.05cm}. $$
  • The second solution results from the symmetry of   $H_{\rm bin}(p)$  to  $p_2 = 1 -p_1 \hspace{0.15cm}\underline{= 0.89}$.



(5)  With  $p = 0.45$  one obtains  $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm bit$.  The relative error with respect to entropy is thus

$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.45)- H_{\rm bin}(p= 0.5)}{H_{\rm bin}(p = 0.5)}= \frac{0.993- 1}{1}\hspace{0.15cm}\underline {= -0.7 \, {\rm \%}} \hspace{0.05cm}.$$
  • The minus sign indicates that the entropy value  $H_{\rm bin}(p) = 0.993\hspace{0.05cm}\rm bit$  is too small.
  • If the simulation had yielded the too large value  $p = 0.55$ , the entropy and also the relative error would be just as large.



(6)    $H_{\rm bin}(p = 0.045) = 0.265\hspace{0.05cm}\rm bit$ is valid.

  • With the result of subtask  (3)   ⇒   $H_{\rm bin}(p = 0.05) = 0.286\hspace{0.05cm}\rm bit$  it follows for the relative error with respect to the entropy:
$$\varepsilon_{H} = \frac{H_{\rm bin}(p = 0.045)- H_{\rm bin}(p= 0.05)}{H_{\rm bin}(p = 0.05)}= \frac{0.265- 0.286}{0.286}\hspace{0.15cm}\underline {= -7.3 \, {\rm \%}} \hspace{0.05cm}.$$
  • The result shows:
  1.  An incorrect determination of the symbol probabilities by  $10\%$  is much more noticeable for  $p = 0.05$  due to the steeper  $H_{\rm bin}(p)$ course than for  $p = 0.5$.
  2.  A too large probability  $p = 0.055$  would have led to  $H_{\rm bin}(p = 0.055) = 0.307\hspace{0.05cm}\rm bit$  and thus to a distortion of  $\varepsilon_H = +7.3\%$. 
  3. In this range, the entropy curve is thus linear (with a good approximation).