Difference between revisions of "Aufgaben:Exercise 3.4: Entropy for Different PMF"

From LNTwww
 
(30 intermediate revisions by 5 users not shown)
Line 1: Line 1:
  
−
{{quiz-Header|Buchseite=Informationstheorie/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
+
{{quiz-Header|Buchseite=Information_Theory/Some_Preliminary_Remarks_on_Two-Dimensional_Random_Variables
 
}}
 
}}
  
−
[[File:P_ID2758__Inf_Z_3_3.png|right|]]
+
[[File:EN_Inf_Z_3_3.png|right|frame|Probability functions, each with  $M = 4$  elements]]
−
In der ersten Zeile der nebenstehenden Tabelle ist die mit „a” bezeichnete Wahrscheinlichkeitsfunktion angegeben. Für dieses $P_X(X)$ soll  soll in der Teilaufgabe (a) die Entropie
+
In the first row of the adjacent table, the probability mass function denoted by  $\rm (a)$  is given in the following.
  
−
$$H_{\rm a}(X) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{X}(X)}\right ]$$
+
For this PMF  $P_X(X) = \big [0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$  the entropy is to be calculated in subtask  '''(1)''' :
 +
:$$H_{\rm a}(X) = {\rm E} \big [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{X}(X)}\big ]= - {\rm E} \big  [ {\rm log}_2 \hspace{0.1cm}{P_{X}(X)}\big ].$$
 +
Since the logarithm to the base  $2$  is used here, the pseudo-unit  "bit"  is to be added.
  
−
berechnet werden. Da hier der Logarithmus zur Basis 2 verwendet wird, ist die Pseudo–Einheit „bit” anzufügen.
+
In the further tasks, some probabilities are to be varied in each case in such a way that the greatest possible entropy results:
 +
 
 +
* By suitably varying  $p_3$  and  $p_4$,  one arrives at the maximum entropy  $H_{\rm b}(X)$  under the condition  $p_1 = 0.1$  and  $p_2 = 0.2$    ⇒   subtask  '''(2)'''.
 +
* By varying  $p_2$  and  $p_3$ appropriately, one arrives at the maximum entropy  $H_{\rm c}(X)$  under the condition  $p_1 = 0.1$  and  $p_4 = 0.4$   ⇒   subtask  '''(3)'''.
 +
* In subtask  '''(4)'''  all four parameters are released for variation,  which are to be determined according to the maximum entropy   ⇒   $H_{\rm max}(X)$ .
  
−
In den weiteren Aufgaben sollen jeweils einige Wahrscheinlichkeiten variiert werden und zwar derart, dass sich jeweils die größtmögliche Entropie ergibt:
 
  
−
:* Durch geeignete Variation von $p_3$ und $p_4$ kommt man zur maximalen Entropie $H_b(X)$ unter der Voraussetzung $p_1 = 0.1$ und $p_2 = 0.2$      $\Rightarrow$ Teilaufgabe (b).
 
  
−
:* Durch geeignete Variation von $p_2$ und $p_3$ kommt man zur maximalen Entropie $H_c(X)$ unter der Voraussetzung $p_1 = 0.1$ und $p_4 = 0.4$      $\Rightarrow$ Teilaufgabe (c).
 
−
 
−
:* In der Teilaufgabe (d) sind alle vier Parameter zur Variation freigegeben, die entsprechend der maximalen Entropie $\Rightarrow$  $H_{max}(X)$  zu bestimmen sind.
 
  
−
'''Hinweis:''' Die Aufgabe bezieht sich auf das [http://en.lntwww.de/Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgr%C3%B6%C3%9Fen Kapitel 3.1]
 
  
  
  
  
 +
Hints:
 +
*The exercise belongs to the chapter  [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Some preliminary remarks on two-dimensional random variables]].
 +
*In particular, reference is made to the page  [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Probability_mass_function_and_entropy|Probability mass function and entropy]].
 +
  
  
−
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
 +
{To which entropy does the probability mass function&nbsp; $P_X(X) = \big [ 0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$ lead?
 +
|type="{}"}
 +
$H_{\rm a}(X) \ = \ $ { 1.846 0.5% } $\ \rm bit$
  
 +
{Let&nbsp; $P_X(X) = \big [ 0.1, \ 0.2, \ p_3, \ p_4\big ]$ apply in general.&nbsp; What entropy is obtained if&nbsp; $p_3$&nbsp; and&nbsp; $p_4$&nbsp; are chosen as best as possible?
 +
|type="{}"}
 +
$H_{\rm b}(X) \ = \ $ { 1.857 0.5% } $\ \rm bit$
  
 +
{ Now let&nbsp; $P_X(X) = \big [ 0.1, \ p_2, \ p_3, \ 0.4 \big ]$.&nbsp; What entropy is obtained if&nbsp; $p_2$&nbsp; and&nbsp; $p_3$&nbsp; are chosen as best as possible?
 +
|type="{}"}
 +
$H_{\rm c}(X) \ = \ $ { 1.861 0.5% } $\ \rm bit$
  
−
Zu welcher Entropie führt $P_X(X) = [ 0.1, 0.2, 0.3, 0.4]$ ?
+
{ What entropy is obtained if all probabilities &nbsp;$(p_1, \ p_2 , \ p_3, \ p_4)$&nbsp; can be chosen as best as possible?
 
|type="{}"}
 
|type="{}"}
−
$H_a(X)$ = { 1.846 1% }
+
$H_{\rm max}(X) \ = \ $ { 2 1% } $\ \rm bit$
−
 
 
  
  
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''1.'''
+
'''(1)'''&nbsp;  With&nbsp; $P_X(X) = \big [ 0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$&nbsp; we get for the entropy:
−
'''2.'''
+
:$$H_{\rm a}(X) =
−
'''3.'''
+
0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} +
−
'''4.'''
+
0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} +
−
'''5.'''
+
0.3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.3} +
−
'''6.'''
+
0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4}
−
'''7.'''
+
\hspace{0.15cm} \underline {= 1.846}  \hspace{0.05cm}.$$
 +
Here (and in the other tasks) the pseudo-unit&nbsp; "bit"&nbsp; is to be added in each case.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; The entropy&nbsp; $H_{\rm b}(X)$&nbsp; can be represented as the sum of two parts&nbsp;  $H_{\rm b1}(X)$&nbsp; and&nbsp; $H_{\rm b2}(X)$,&nbsp; with:
 +
:$$H_{\rm b1}(X) =
 +
0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} +
 +
0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} = 0.797 \hspace{0.05cm},$$
 +
:$$H_{\rm b2}(X)  =
 +
p_3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p_3} +
 +
(0.7-p_3) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.7-p_3} \hspace{0.05cm}.$$
 +
 
 +
*The second function is maximum for&nbsp; $p_3 = p_4 = 0.35$.&nbsp; A similar relationship has been found for the binary entropy function. &nbsp;
 +
*Thus one obtains:
 +
 
 +
:$$H_{\rm b2}(X) = 2 \cdot
 +
p_3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p_3} =
 +
0.7 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.35} = 1.060 $$
 +
:$$ \Rightarrow \hspace{0.3cm} H_{\rm b}(X) = H_{\rm b1}(X) + H_{\rm b2}(X) = 0.797 + 1.060 \hspace{0.15cm} \underline {= 1.857}  \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Analogous to subtask&nbsp; '''(2)''',&nbsp; $p_1 = 0.1$&nbsp; and&nbsp; $p_4 = 0.4$&nbsp; yield the maximum for&nbsp; $p_2 = p_3  = 0.25$:
 +
:$$H_{\rm c}(X) =
 +
0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} +
 +
2 \cdot 0.25 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.25} +
 +
0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4}
 +
\hspace{0.15cm} \underline {= 1.861}  \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; The maximum entropy for the symbol range&nbsp; $M=4$&nbsp; is obtained for equal probabilities, i.e. for&nbsp; $p_1 = p_2 = p_3 = p_4 = 0.25$:
 +
:$$H_{\rm max}(X) =
 +
{\rm log}_2 \hspace{0.1cm} M
 +
\hspace{0.15cm} \underline {= 2}  \hspace{0.05cm}.$$
 +
 
 +
*The difference of the entropies according to&nbsp; '''(4)'''&nbsp; and&nbsp; '''(3)'''&nbsp; gives&nbsp; ${\rm \Delta} H(X) = 0.139 \ \rm bit$.&nbsp;  Here:
 +
:$${\rm \Delta}  H(X) = 1-
 +
0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} -
 +
0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4}
 +
\hspace{0.05cm}.$$
 +
 
 +
*With the binary entropy function
 +
 
 +
:$$H_{\rm bin}(p) =
 +
p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} +
 +
(1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}$$
 +
 
 +
:can also be written for this:
 +
 
 +
:$${\rm \Delta} H(X) = 0.5 \cdot \big [ 1- H_{\rm bin}(0.2) \big ] =
 +
0.5 \cdot \big [ 1- 0.722 \big ] = 0.139
 +
\hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
 
 +
 +
 
 +
 
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
−
[[Category:Aufgaben zu Informationstheorie|^3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen^]]
+
[[Category:Information Theory: Exercises|^3.1 General Information on 2D Random Variables^]]

Latest revision as of 09:13, 24 September 2021

Probability functions, each with  $M = 4$  elements

In the first row of the adjacent table, the probability mass function denoted by  $\rm (a)$  is given in the following.

For this PMF  $P_X(X) = \big [0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$  the entropy is to be calculated in subtask  (1) :

$$H_{\rm a}(X) = {\rm E} \big [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{X}(X)}\big ]= - {\rm E} \big [ {\rm log}_2 \hspace{0.1cm}{P_{X}(X)}\big ].$$

Since the logarithm to the base  $2$  is used here, the pseudo-unit  "bit"  is to be added.

In the further tasks, some probabilities are to be varied in each case in such a way that the greatest possible entropy results:

  • By suitably varying  $p_3$  and  $p_4$,  one arrives at the maximum entropy  $H_{\rm b}(X)$  under the condition  $p_1 = 0.1$  and  $p_2 = 0.2$   ⇒   subtask  (2).
  • By varying  $p_2$  and  $p_3$ appropriately, one arrives at the maximum entropy  $H_{\rm c}(X)$  under the condition  $p_1 = 0.1$  and  $p_4 = 0.4$   ⇒   subtask  (3).
  • In subtask  (4)  all four parameters are released for variation,  which are to be determined according to the maximum entropy   ⇒   $H_{\rm max}(X)$ .





Hints:


Questions

1

To which entropy does the probability mass function  $P_X(X) = \big [ 0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$ lead?

$H_{\rm a}(X) \ = \ $

$\ \rm bit$

2

Let  $P_X(X) = \big [ 0.1, \ 0.2, \ p_3, \ p_4\big ]$ apply in general.  What entropy is obtained if  $p_3$  and  $p_4$  are chosen as best as possible?

$H_{\rm b}(X) \ = \ $

$\ \rm bit$

3

Now let  $P_X(X) = \big [ 0.1, \ p_2, \ p_3, \ 0.4 \big ]$.  What entropy is obtained if  $p_2$  and  $p_3$  are chosen as best as possible?

$H_{\rm c}(X) \ = \ $

$\ \rm bit$

4

What entropy is obtained if all probabilities  $(p_1, \ p_2 , \ p_3, \ p_4)$  can be chosen as best as possible?

$H_{\rm max}(X) \ = \ $

$\ \rm bit$


Solution

Solution

(1)  With  $P_X(X) = \big [ 0.1, \ 0.2, \ 0.3, \ 0.4 \big ]$  we get for the entropy:

$$H_{\rm a}(X) = 0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} + 0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} + 0.3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.3} + 0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4} \hspace{0.15cm} \underline {= 1.846} \hspace{0.05cm}.$$

Here (and in the other tasks) the pseudo-unit  "bit"  is to be added in each case.


(2)  The entropy  $H_{\rm b}(X)$  can be represented as the sum of two parts  $H_{\rm b1}(X)$  and  $H_{\rm b2}(X)$,  with:

$$H_{\rm b1}(X) = 0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} + 0.2 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.2} = 0.797 \hspace{0.05cm},$$
$$H_{\rm b2}(X) = p_3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p_3} + (0.7-p_3) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.7-p_3} \hspace{0.05cm}.$$
  • The second function is maximum for  $p_3 = p_4 = 0.35$.  A similar relationship has been found for the binary entropy function.  
  • Thus one obtains:
$$H_{\rm b2}(X) = 2 \cdot p_3 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p_3} = 0.7 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.35} = 1.060 $$
$$ \Rightarrow \hspace{0.3cm} H_{\rm b}(X) = H_{\rm b1}(X) + H_{\rm b2}(X) = 0.797 + 1.060 \hspace{0.15cm} \underline {= 1.857} \hspace{0.05cm}.$$


(3)  Analogous to subtask  (2),  $p_1 = 0.1$  and  $p_4 = 0.4$  yield the maximum for  $p_2 = p_3 = 0.25$:

$$H_{\rm c}(X) = 0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} + 2 \cdot 0.25 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.25} + 0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4} \hspace{0.15cm} \underline {= 1.861} \hspace{0.05cm}.$$


(4)  The maximum entropy for the symbol range  $M=4$  is obtained for equal probabilities, i.e. for  $p_1 = p_2 = p_3 = p_4 = 0.25$:

$$H_{\rm max}(X) = {\rm log}_2 \hspace{0.1cm} M \hspace{0.15cm} \underline {= 2} \hspace{0.05cm}.$$
  • The difference of the entropies according to  (4)  and  (3)  gives  ${\rm \Delta} H(X) = 0.139 \ \rm bit$.  Here:
$${\rm \Delta} H(X) = 1- 0.1 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.1} - 0.4 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.4} \hspace{0.05cm}.$$
  • With the binary entropy function
$$H_{\rm bin}(p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}$$
can also be written for this:
$${\rm \Delta} H(X) = 0.5 \cdot \big [ 1- H_{\rm bin}(0.2) \big ] = 0.5 \cdot \big [ 1- 0.722 \big ] = 0.139 \hspace{0.05cm}.$$





Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_3.4:_Entropy_for_Different_PMF&oldid=41385"
  • Powered by MediaWiki