View source for Information Theory/Different Entropy Measures of Two-Dimensional Random Variables

 
{{Header
|Untermenü=Mutual Information Between Two Discrete Random Variables
|Vorherige Seite=Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
|Nächste Seite=Anwendung auf die Digitalsignalübertragung
}}


==Definition of entropy using supp(<i>P<sub>XY</sub></i>)== 
<br> 
We briefly summarize the results of the last chapter again, assuming the two-dimensional random variable&nbsp; $XY$&nbsp; with the probability mass function&nbsp; $P_{XY}(X,\ Y)$&nbsp;.&nbsp; At the same time we use the notation
 
:$${\rm supp} (P_{XY}) = \big \{ \hspace{0.05cm}(x,\ y) \in XY \hspace{0.05cm},
\hspace{0.3cm} {\rm where} \hspace{0.15cm} P_{XY}(X,\ Y) \ne 0 \hspace{0.05cm} \big \} \hspace{0.05cm};$$

{{BlaueBox|TEXT=
$\text{Summarizing the last chapter:}$&nbsp; With this subset&nbsp; $\text{supp}(P_{XY}) ⊂ P_{XY}$,&nbsp; the following holds for
*the&nbsp; &raquo;'''joint entropy'''&laquo;&nbsp;:
 
:$$H(XY) = {\rm E}\hspace{-0.1cm} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{XY}(X, Y)}\right ] =\hspace{-0.2cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY}\hspace{-0.05cm})} 
 \hspace{-0.6cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{XY}(x, y)} \hspace{0.05cm}.$$

*the&nbsp; &raquo;'''entropies of the one-dimensional random variables'''&laquo;&nbsp; $X$&nbsp; and&nbsp; $Y$:
  
:$$H(X) = {\rm E}\hspace{-0.1cm} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{X}(X)}\right ] =\hspace{-0.2cm} \sum_{x \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{X})} 
 \hspace{-0.2cm} P_{X}(x) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{X}(x)} \hspace{0.05cm},$$
:$$H(Y) = {\rm E}\hspace{-0.1cm} \left [ {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{Y}(Y)}\right ] =\hspace{-0.2cm} \sum_{y \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{Y})} 
 \hspace{-0.2cm} P_{Y}(y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{Y}(y)} \hspace{0.05cm}.$$}}


{{GraueBox|TEXT=
$\text{Example 1:}$&nbsp; We refer again to the examples on the&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{joint probability and joint entropy}$]]&nbsp; in the last chapter.&nbsp; 

For the two-dimensional probability mass function&nbsp; $P_{RB}(R, B)$&nbsp; in&nbsp;  [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{Example 5}$]]&nbsp; with the parameters
*$R$ &nbsp; &rArr; &nbsp;  points of the red cube,
*$B$ &nbsp; &rArr; &nbsp;  points of the blue cube,


the sets&nbsp; $P_{RB}$&nbsp; and&nbsp; $\text{supp}(P_{RB})$&nbsp; are identical.&nbsp; Here, all&nbsp; $6^2 = 36$&nbsp; squares are occupied by non-zero values.

For the two-dimensional probability mass function&nbsp; $P_{RS}(R, S)$&nbsp;  in&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{Example 6}$]]&nbsp; with the parameters  
*$R$ &nbsp; &rArr; &nbsp;  points of the red cube,
*$S = R + B$ &nbsp; &rArr; &nbsp; sum of both cubes,


there are&nbsp; $6 · 11 = 66$ squares, many of which, however, are empty, i.e. stand for the probability&nbsp; "0" .
*The subset&nbsp; $\text{supp}(P_{RS})$&nbsp;, on the other hand, contains only the&nbsp; $36$&nbsp; shaded squares with non-zero probabilities.
*The entropy remains the same no matter whether one averages over all elements of&nbsp; $P_{RS}$&nbsp; or only over the elements of &nbsp; $\text{supp}(P_{RS})$&nbsp; since for&nbsp; $x → 0$&nbsp; the limit is&nbsp; $x · \log_2 ({1}/{x}) = 0$.}}


==Conditional probability and conditional entropy == 	 
<br> 
In the book&nbsp; "Theory of Stochastic Signals"&nbsp; the following &nbsp; [[Theory_of_Stochastic_Signals/Statistical_Dependence_and_Independence#Conditional_probability|$\text{conditional probabilities}$]]&nbsp;  were given for the case of two events&nbsp; $X$&nbsp; and&nbsp; $Y$&nbsp;  ⇒  &nbsp; &raquo;'''Bayes' theorem'''&laquo;:
 
:$${\rm Pr} (X \hspace{-0.05cm}\mid \hspace{-0.05cm} Y)  = \frac{{\rm Pr} (X \cap  Y)}{{\rm Pr} (Y)} \hspace{0.05cm}, \hspace{0.5cm}
{\rm Pr} (Y \hspace{-0.05cm}\mid \hspace{-0.05cm} X)  = \frac{{\rm Pr} (X \cap  Y)}{{\rm Pr} (X)} \hspace{0.05cm}.$$

Applied to probability mass functions, one thus obtains:
 
:$$P_{\hspace{0.03cm}X \mid \hspace{0.03cm} Y} (X \hspace{-0.05cm}\mid \hspace{-0.05cm} Y)  = \frac{P_{XY}(X, Y)}{P_{Y}(Y)} \hspace{0.05cm}, \hspace{0.5cm} 
P_{\hspace{0.03cm}Y \mid \hspace{0.03cm} X} (Y \hspace{-0.05cm}\mid \hspace{-0.05cm} X)  =  \frac{P_{XY}(X, Y)}{P_{X}(X)} \hspace{0.05cm}.$$

Analogous to the&nbsp; [[Information_Theory/Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen#Definition_of_entropy_using_supp.28PXY.29|$\text{joint entropy}$]]&nbsp; $H(XY)$&nbsp;, the following entropy functions can be derived here:

{{BlaueBox|TEXT=
$\text{Definitions:}$&nbsp;
*The&nbsp; &raquo;'''conditional entropy'''&laquo; of the random variable&nbsp; $X$&nbsp; under condition&nbsp; $Y$&nbsp; is:
 
:$$H(X \hspace{-0.05cm}\mid \hspace{-0.05cm} Y) = {\rm E} \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm}\frac{1}{P_{\hspace{0.03cm}X \mid \hspace{0.03cm} Y} (X \hspace{-0.05cm}\mid \hspace{-0.05cm} Y)}\right ] = \hspace{-0.2cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY}\hspace{-0.08cm})} 
 \hspace{-0.6cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.03cm}X \mid \hspace{0.03cm} Y} (x \hspace{-0.05cm}\mid \hspace{-0.05cm} y)}=\hspace{-0.2cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY}\hspace{-0.08cm})} 
 \hspace{-0.6cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_{Y}(y)}{P_{XY}(x, y)}
 \hspace{0.05cm}.$$

*Similarly, for the&nbsp; &raquo;'''second conditional entropy'''&laquo; we obtain:
 
:$$H(Y \hspace{-0.1cm}\mid \hspace{-0.05cm} X) = {\rm E} \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm}\frac{1}{P_{\hspace{0.03cm}Y\hspace{0.03cm} \mid \hspace{0.01cm} X} (Y \hspace{-0.08cm}\mid \hspace{-0.05cm}X)}\right ] =\hspace{-0.2cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY}\hspace{-0.08cm})} 
 \hspace{-0.6cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.03cm}Y\hspace{-0.03cm} \mid \hspace{-0.01cm} X} (y \hspace{-0.05cm}\mid \hspace{-0.05cm} x)}=\hspace{-0.2cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY}\hspace{-0.08cm})} 
 \hspace{-0.6cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_{X}(x)}{P_{XY}(x, y)}
 \hspace{0.05cm}.$$}}


In the argument of the logarithm function there is always a conditional probability function &nbsp; ⇒ &nbsp; $P_{X\hspace{0.03cm}| \hspace{0.03cm}Y}(·)$&nbsp; or&nbsp; $P_{Y\hspace{0.03cm}|\hspace{0.03cm}X}(·)$&nbsp; resp.,&nbsp; while the joint probability &nbsp; ⇒ &nbsp; $P_{XY}(·)$ is needed for the expectation value formation.

For the conditional entropies, there are the following limitations:
*Both&nbsp; $H(X|Y)$&nbsp; and&nbsp; $H(Y|X)$&nbsp; are always greater than or equal to zero.&nbsp; From&nbsp; $H(X|Y) = 0$&nbsp; it follows directly&nbsp; $H(Y|X) = 0$.&nbsp; <br>Both are only possible for &nbsp; [[Theory_of_Stochastic_Signals/Set_Theory_Basics#Disjoint_sets|$\text{disjoint sets}$]]&nbsp; $X$&nbsp; and&nbsp; $Y$.
*$H(X|Y) ≤ H(X)$&nbsp; and&nbsp; $H(Y|X) ≤ H(Y)$ always apply.&nbsp; These statements are plausible if one realizes that one can also use&nbsp; "uncertainty"&nbsp; synonymously for&nbsp; "entropy".&nbsp; For: &nbsp; The uncertainty with respect to the quantity&nbsp;  $X$&nbsp; cannot be increased by knowing&nbsp; $Y$.&nbsp; 
*Except in the case of statistical independence   &nbsp; ⇒ &nbsp;   $H(X|Y) = H(X)$&nbsp;, &nbsp; $H(X|Y) < H(X)$ always holds.&nbsp; Because of&nbsp; $H(X) ≤ H(XY)$&nbsp; and&nbsp; $H(Y) ≤ H(XY)$&nbsp;,&nbsp; therefore also&nbsp; $H(X|Y) ≤ H(XY)$&nbsp; and&nbsp; $H(Y|X) ≤ H(XY)$&nbsp;  hold.&nbsp; Thus, '''a conditional entropy can never become larger than the joint entropy'''.


{{GraueBox|TEXT=
$\text{Example 2:}$&nbsp; We consider the joint probabilities&nbsp; $P_{RS}(·)$&nbsp; of our dice experiment, which were determined in the&nbsp; [[Information_Theory/Some_Preliminary_Remarks_on_Two-Dimensional_Random_Variables#Joint_probability_and_joint_entropy|"last chapter"]]&nbsp; as&nbsp; $\text{Example 6}$.&nbsp; The corresponding &nbsp;$P_{RS}(·)$&nbsp; is given again in the middle of the following graph.

[[File:P_ID2764__Inf_T_3_2_S3.png|right|frame|Joint probabilities&nbsp; $P_{RS}$&nbsp; and conditional probabilities&nbsp;  $P_{S \vert R}$&nbsp; and&nbsp; $P_{R \vert S}$]]

The two conditional probability functions are drawn on the outside:

$\text{On the left}$&nbsp; you see the conditional probability mass function&nbsp; 
:$$P_{S \vert R}(⋅) = P_{SR}(⋅)/P_R(⋅).$$
*Because of&nbsp; $P_R(R) = \big [1/6, \ 1/6, \ 1/6, \ 1/6, \ 1/6, \ 1/6 \big ]$&nbsp; the probability&nbsp; $1/6$&nbsp; is in all shaded fields &nbsp; 
*That means: &nbsp; $\text{supp}(P_{S\vert R}) = \text{supp}(P_{R\vert S})$&nbsp; .&nbsp; 
*From this follows for the conditional entropy:
 
:$$H(S \hspace{-0.1cm}\mid \hspace{-0.13cm} R) = \hspace{-0.2cm} \sum_{(r, s) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{RS})} 
 \hspace{-0.6cm} P_{RS}(r, s) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{P_{\hspace{0.03cm}S \hspace{0.03cm} \mid \hspace{0.03cm} R} (s \hspace{-0.05cm}\mid \hspace{-0.05cm} r)} $$
:$$\Rightarrow \hspace{0.3cm}H(S \hspace{-0.1cm}\mid \hspace{-0.13cm} R) =
36 \cdot \frac{1}{36} \cdot {\rm log}_2 \hspace{0.1cm} (6) = 2.585\ {\rm bit}
\hspace{0.05cm}.$$

$\text{On the right}$,&nbsp; $P_{R\vert S}(⋅) = P_{RS}(⋅)/P_S(⋅)$&nbsp; is given with&nbsp; $P_S(⋅)$&nbsp; according to&nbsp; $\text{Example 6}$.&nbsp; 
*$\text{supp}(P_{R\vert S}) = \text{supp}(P_{S\vert R})$ &nbsp; ⇒ &nbsp;same non-zero fields result. 
*However, the probability values now increase continuously from the centre&nbsp; $(1/6)$&nbsp;  towards the edges up to&nbsp; $1$&nbsp; in the corners. 
*It follows that:
 
:$$H(R \hspace{-0.1cm}\mid \hspace{-0.13cm} S)  = \frac{1}{36} \cdot {\rm log}_2 \hspace{0.1cm} (6) +
\frac{2}{36} \cdot  \sum_{i=1}^5 \big [ i \cdot {\rm log}_2 \hspace{0.1cm} (i) \big ]= 1.896\ {\rm bit} \hspace{0.05cm}.$$

On the other hand, for the conditional probabilities of the 2D random variable&nbsp; $RB$&nbsp; according to&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{Example 5}$]],&nbsp; one obtains because of&nbsp; $P_{RB}(⋅) = P_R(⋅) · P_B(⋅)$:
 
:$$\begin{align*}H(B \hspace{-0.1cm}\mid \hspace{-0.13cm} R)  \hspace{-0.15cm} & =  \hspace{-0.15cm} H(B) = {\rm log}_2 \hspace{0.1cm} (6) = 2.585\ {\rm bit} \hspace{0.05cm},\\
H(R \hspace{-0.1cm}\mid \hspace{-0.13cm} B)  \hspace{-0.15cm} & = \hspace{-0.15cm} H(R) = {\rm log}_2 \hspace{0.1cm} (6) = 2.585\ {\rm bit} \hspace{0.05cm}.\end{align*}$$}}

	 

==Mutual information between two random variables== 	 
<br> 
We consider the two-dimensional random variable&nbsp; $XY$&nbsp; with PMF&nbsp; $P_{XY}(X, Y)$.&nbsp;Let the one-dimensional functions&nbsp; $P_X(X)$&nbsp; and&nbsp; $P_Y(Y)$ also be known. 

Now the following questions arise:
*How does the knowledge of the random variable&nbsp; $Y$&nbsp; reduce the uncertainty with respect to&nbsp; $X$?
*How does the knowledge of the random variable&nbsp; $X$&nbsp; reduce the uncertainty with respect to&nbsp; $Y$?


To answer this question, we need a definition that is substantial for information theory:

{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; The&nbsp; &raquo;'''mutual information'''&laquo; between the random variables&nbsp; $X$&nbsp; and&nbsp; $Y$ –  both over the same alphabet – is given as follows:
 
:$$I(X;\ Y) = {\rm E} \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.08cm} \frac{P_{XY}(X, Y)}
{P_{X}(X) \cdot P_{Y}(Y) }\right ] =\hspace{-0.25cm} \sum_{(x, y) \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{XY})} 
 \hspace{-0.8cm} P_{XY}(x, y) \cdot {\rm log}_2 \hspace{0.08cm} \frac{P_{XY}(x, y)}
{P_{X}(x) \cdot P_{Y}(y) } \hspace{0.01cm}.$$

A comparison with the&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Introductory_example_on_the_statistical_dependence_of_random_variables|"last chapter"]]&nbsp; shows that the mutual information can also be written as a&nbsp; [[Information_Theory/Some_Preliminary_Remarks_on_Two-Dimensional_Random_Variables#Informational_divergence_-_Kullback-Leibler_distance|$\text{Kullback–Leibler distance}$]]&nbsp; between the two-dimensional probability mass function&nbsp; $P_{XY}$&nbsp; and the product&nbsp; $P_X · P_Y$&nbsp; :
 
:$$I(X;Y) = D(P_{XY} \hspace{0.05cm}\vert \vert \hspace{0.05cm} P_X \cdot P_Y) \hspace{0.05cm}.$$

It is thus obvious that&nbsp; $I(X;\ Y) ≥ 0$&nbsp; always holds.&nbsp; Because of the symmetry, &nbsp; $I(Y;\ X)$ = $I(X;\ Y)$ is also true.}}


By splitting the&nbsp; $\log_2$ argument according to
 
:$$I(X;Y) = {\rm E} \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm} \frac{1}
{P_{X}(X)  }\right ] - {\rm E} \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm} \frac
{P_{Y}(Y) }{P_{XY}(X, Y)} \right ] $$

is obtained using&nbsp; $P_{X|Y}(\cdot) = P_{XY}(\cdot)/P_Y(Y)$:
 
:$$I(X;Y) = H(X) - H(X \hspace{-0.1cm}\mid \hspace{-0.1cm} Y) \hspace{0.05cm}.$$

*This means: &nbsp; The uncertainty regarding the random quantity&nbsp; $X$  &nbsp; ⇒  &nbsp;  entropy&nbsp; $H(X)$&nbsp; decreases by the magnitude&nbsp; $H(X|Y)$&nbsp; when&nbsp; $Y$ is known.&nbsp; The remainder is the mutual information&nbsp; $I(X; Y)$.
*With a different splitting, one arrives at the result
:$$I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) \hspace{0.05cm}.$$
*Ergo: &nbsp; The mutual information&nbsp; $I(X; Y)$&nbsp; is symmetrical  &nbsp; ⇒ &nbsp;  $X$&nbsp; says just as much about&nbsp; $Y$&nbsp; as&nbsp; $Y$&nbsp; says about&nbsp; $X$  &nbsp; ⇒ &nbsp; "mutual".&nbsp; The semicolon indicates equality.


{{BlaueBox|TEXT=
$\text{Conclusion:}$&nbsp; 
Often the equations mentioned here are clarified by a diagram, as in the following examples.&nbsp; <br>From this you can see that the following equations also apply:
 
:$$I(X;\ Y) = H(X) + H(Y) - H(XY) \hspace{0.05cm},$$
:$$I(X;\ Y) = H(XY) - 
H(X \hspace{-0.1cm}\mid \hspace{-0.1cm} Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)
\hspace{0.05cm}.$$}}


{{GraueBox|TEXT=
$\text{Example 3:}$&nbsp; We return&nbsp; (for the last time)&nbsp; to the&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Introductory_example_on_the_statistical_dependence_of_random_variables|$\text{dice experiment}$]]&nbsp; with the red&nbsp; $(R)$&nbsp; and blue&nbsp; $(B)$&nbsp; cube.&nbsp;  The random variable&nbsp; $S$&nbsp; gives the sum of the two dice:&nbsp; $S = R + B$.&nbsp;
Here we consider the 2D random variable&nbsp; $RS$.&nbsp; 

In earlier examples we calculated
*the entropies&nbsp; $H(R) = 2.585 \ \rm  bit$&nbsp; and&nbsp; $H(S) = 3.274 \ \rm bit$ &nbsp; ⇒  &nbsp;[[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{Example 6}$]]&nbsp; in the last chapter,
*the join entropies&nbsp; $H(RS) = 5.170 \ \rm bit$  &nbsp; ⇒  &nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Joint_probability_and_joint_entropy|$\text{Example 6}$]]&nbsp; in the last chapter,
*the conditional entropies&nbsp; $H(S \hspace{0.05cm} \vert \hspace{0.05cm} R) = 2.585 \ \rm bit$&nbsp; and&nbsp; $H(R \hspace{0.05cm} \vert \hspace{0.05cm}  S) = 1.896 \ \rm bit$  &nbsp; ⇒  &nbsp;  [[Information_Theory/Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen#Conditional_probability_and_conditional_entropy|$\text{Example 2}$]]&nbsp; in the previous section.

[[File:P_ID2765__Inf_T_3_2_S3_neu.png|frame|Diagram of all entropies of the "dice experiment" ]]

<br>These quantities are compiled in the graph, with the random quantity&nbsp; $R$&nbsp; marked by the basic colour "red" and the sum&nbsp; $S$&nbsp; marked by the basic colour "green" .&nbsp; Conditional entropies are shaded.&nbsp;
One can see from this representation:
*The entropy&nbsp; $H(R) = \log_2 (6) = 2.585\ \rm bit$&nbsp; is exactly half as large as the joint entropy&nbsp; $H(RS)$.&nbsp; Because:&nbsp; If one knows&nbsp; $R$,&nbsp; then&nbsp; $S$&nbsp; provides exactly the same information as the random quantity&nbsp; $B$, namely&nbsp; $H(S \hspace{0.05cm} \vert \hspace{0.05cm}  R) = H(B) = \log_2 (6) = 2.585\ \rm bit$.&nbsp; 
*'''Note''': &nbsp; $H(R)$ = $H(S \hspace{0.05cm} \vert \hspace{0.05cm}  R)$&nbsp; '''only applies in this example, not in general'''.
*As expected, here the entropy&nbsp; $H(S) = 3.274 \ \rm bit$&nbsp; is greater than&nbsp; $H(R)= 2.585\ \rm bit$.&nbsp; Because of&nbsp; $H(S) + H(R \hspace{0.05cm} \vert \hspace{0.05cm}  S) = H(R) + H(S \hspace{0.05cm} \vert \hspace{0.05cm}  R)$&nbsp;,&nbsp; $H(R \hspace{0.05cm} \vert \hspace{0.05cm}  S)$&nbsp; must therefore be smaller than&nbsp; $H(S \hspace{0.05cm} \vert \hspace{0.05cm} R)$&nbsp; by &nbsp; $I(R;\ S) = 0.689 \ \rm bit$&nbsp;. &nbsp; $H(R)$&nbsp; is also smaller than&nbsp; $H(S)$ by &nbsp; $I(R;\ S) = 0.689 \ \rm bit$&nbsp;.
*The mutual information between the random variables&nbsp; $R$&nbsp; and&nbsp; $S$&nbsp; also results from the equation
:$$I(R;\ S) = H(R) + H(S) - H(RS) =  2.585\ {\rm bit} + 3.274\ {\rm bit} - 5.170\ {\rm bit} = 0.689\ {\rm bit} \hspace{0.05cm}. $$}}


==Conditional mutual information  ==	 
<br> 
We now consider three random variables&nbsp; $X$,&nbsp; $Y$&nbsp; and&nbsp; $Z$, that can be related to each other.
{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp; The &nbsp; &raquo;'''conditional mutual information'''&laquo; &nbsp;  between the random variables&nbsp; $X$&nbsp; and&nbsp; $Y$&nbsp; '''for a given'''&nbsp; $Z = z$&nbsp; is as follows:
 
:$$I(X;Y \hspace{0.05cm}\vert\hspace{0.05cm} Z = z) =  H(X\hspace{0.05cm}\vert\hspace{0.05cm} Z = z) - H(X\vert\hspace{0.05cm}Y ,\hspace{0.05cm} Z = z) \hspace{0.05cm}.$$

One denotes as the conditional&nbsp; &raquo;'''conditional mutual information'''&laquo;&nbsp; between the random variables&nbsp; $X$&nbsp; and&nbsp; $Y$&nbsp; for the random variable&nbsp; $Z$&nbsp; '''in general'''&nbsp; <br>after averaging over all&nbsp; $z \in Z$:
 
:$$I(X;Y \hspace{0.05cm}\vert\hspace{0.05cm} Z ) =  H(X\hspace{0.05cm}\vert\hspace{0.05cm} Z ) - H(X\vert\hspace{0.05cm}Y  Z )= \hspace{-0.3cm}
\sum_{z \hspace{0.1cm}\in \hspace{0.1cm}{\rm supp} (P_{Z})} \hspace{-0.25cm} P_{Z}(z) \cdot  
I(X;Y \hspace{0.05cm}\vert\hspace{0.05cm} Z = z) 
\hspace{0.05cm}.$$

$P_Z(Z)$&nbsp; is the probability mass function&nbsp; $\rm  (PMF)$&nbsp; of the random variable&nbsp; $Z$&nbsp; and&nbsp; $P_Z(z)$&nbsp; is the&nbsp; &raquo;'''probability'''&laquo;&nbsp; for the realization&nbsp; $Z = z$.}}


{{BlaueBox|TEXT=
$\text{Please note:}$&nbsp; 
*For the conditional entropy, as is well known, the relation &nbsp; $H(X\hspace{0.05cm}\vert\hspace{0.05cm}Z) ≤ H(X)$&nbsp; holds. 
*For the mutual information, this relation does not necessarily hold: <br> &nbsp; &nbsp; $I(X; Y\hspace{0.05cm}\vert\hspace{0.05cm}Z)$&nbsp; can be&nbsp; '''smaller, equal, but also larger than'''&nbsp; $I(X; Y)$.}}


[[File:P_ID2824__Inf_T_3_2_S4a.png|right|frame|2D PMF&nbsp; $P_{XZ}$ ]]
{{GraueBox|TEXT=
$\text{Example 4:}$&nbsp; 
We consider the binary random variables&nbsp; $X$,&nbsp; $Y$&nbsp; and&nbsp; $Z$&nbsp; with the following properties:
* $X$&nbsp; and&nbsp; $Y$&nbsp; be statistically independent.&nbsp; Let the following be true for their probability mass functions:  
:$$P_X(X) = \big [1/2, \ 1/2 \big],  \hspace{0.2cm} P_Y(Y) = \big[1– p, \ p \big] \   ⇒  \  H(X) = 1\ {\rm bit},  \hspace{0.2cm}  H(Y) = H_{\rm bin}(p).$$
* $Z$&nbsp; is the modulo-2 sum of&nbsp; $X$&nbsp; and&nbsp; $Y$: &nbsp;   $Z = X ⊕ Y$.


From the joint probability mass function&nbsp; $P_{XZ}$&nbsp; according to the upper graph, it follows:
*Summing the column probabilities gives&nbsp; <br> &nbsp; &nbsp; $P_Z(Z) = \big [1/2, \  1/2 \big ]$ &nbsp;  ⇒ &nbsp; $H(Z) = 1\ {\rm bit}.$
* $X$&nbsp; and&nbsp; $Z$&nbsp; are also statistically independent, since for the 2D PMF  holds&nbsp; <br> &nbsp; &nbsp; $P_{XZ}(X, Z) = P_X(X) · P_Z(Z)$&nbsp;.&nbsp; 
[[File:P_ID2826__Inf_T_3_2_S4b.png|right|frame|Conditional  2D PMF $P_{X\hspace{0.05cm}\vert\hspace{0.05cm}YZ}$]]

*It follows that: <br> &nbsp; &nbsp; $H(Z\hspace{0.05cm}\vert\hspace{0.05cm}  X) = H(Z),\hspace{0.5cm}(X \hspace{0.05cm}\vert\hspace{0.05cm}  Z) = H(X),\hspace{0.5cm} I(X; Z) = 0.$
<br>From the conditional probability mass function&nbsp; $P_{X\vert YZ}$&nbsp; according to the graph below, we can calculate:
* $H(X\hspace{0.05cm}\vert\hspace{0.05cm} YZ) = 0$,&nbsp; since all&nbsp; $P_{X\hspace{0.05cm}\vert\hspace{0.05cm} YZ}$ entries are&nbsp; $0$&nbsp; or&nbsp; $1$  &nbsp;  ⇒ &nbsp;  "conditional entropy",
* $I(X; YZ) = H(X) - H(X\hspace{0.05cm}\vert\hspace{0.05cm} YZ) = H(X)= 1 \ {\rm bit}$ &nbsp;  ⇒ &nbsp;   "mutual information",
* $I(X; Y\vert Z) = H(X\hspace{0.05cm}\vert\hspace{0.05cm} Z) =H(X)=1 \ {\rm bit} $  &nbsp;  ⇒ &nbsp;   "conditional mutual information".


In the present example: 

'''The conditional mutual information'''&nbsp; $I(X; Y\hspace{0.05cm}\vert\hspace{0.05cm} Z) = 1$&nbsp; '''is greater than the conventional mutual information''' &nbsp;$I(X; Y) = 0$. }}

 	
	 
==Chain rule of the mutual information == 	
<br> 
So far we have only considered the mutual information between two one-dimensional random variables.&nbsp; Now we extend the definition to a total of&nbsp; $n + 1$&nbsp; random variables, which, only for reasons of representation, we denote with&nbsp; $X_1$,&nbsp; ... ,&nbsp; $X_n$&nbsp; and&nbsp; $Z$&nbsp; .&nbsp; Then applies:

{{BlaueBox|TEXT=
$\text{Chain rule of mutual information:}$&nbsp;
 
The mutual information between the&nbsp; $n$–dimensional random variable&nbsp; $X_1 X_2  \hspace{0.05cm}\text{...} \hspace{0.05cm}  X_n$&nbsp; and the random variable&nbsp; $Z$&nbsp; can be represented and calculated as follows:
 
:$$I(X_1\hspace{0.05cm}X_2\hspace{0.05cm}\text{...} \hspace{0.1cm}X_n;Z) = 
I(X_1;Z) + I(X_2;Z \vert X_1) + \hspace{0.05cm}\text{...} \hspace{0.1cm}+
I(X_n;Z\vert X_1\hspace{0.05cm}X_2\hspace{0.05cm}\text{...} \hspace{0.1cm}X_{n-1}) = \sum_{i = 1}^{n}
I(X_i;Z \vert X_1\hspace{0.05cm}X_2\hspace{0.05cm}\text{...} \hspace{0.1cm}X_{i-1})
\hspace{0.05cm}.$$

$\text{Proof:}$&nbsp;
We restrict ourselves here to the case&nbsp; $n = 2$, i.e. to a total of three random variables, and replace&nbsp; $X_1$&nbsp; by $X$ and&nbsp; $X_2$&nbsp; by&nbsp;  $Y$.&nbsp; Then we obtain:
 
:$$\begin{align*}I(X\hspace{0.05cm}Y;Z)  & = H(XY) - H(XY\hspace{0.05cm} \vert \hspace{0.05cm}Z) = \\
& =   \big [  H(X)+ H(Y\hspace{0.05cm} \vert \hspace{0.05cm} X)\big ]  - \big [  H(X\hspace{0.05cm} \vert \hspace{0.05cm} Z) + H(Y\hspace{0.05cm} \vert \hspace{0.05cm} XZ)\big ]  =\\ 
& =   \big [  H(X)- H(X\hspace{0.05cm} \vert \hspace{0.05cm} Z)\big ]  - \big [  H(Y\hspace{0.05cm} \vert \hspace{0.05cm} X) + H(Y\hspace{0.05cm} \vert \hspace{0.05cm}XZ)\big ]=\\
& =  I(X;Z) + I(Y;Z \hspace{0.05cm} \vert \hspace{0.05cm} X) \hspace{0.05cm}.\end{align*}$$}}


*From this equation one can see that the relation &nbsp;$I(X Y; Z) ≥ I(X; Z)$&nbsp; is always given. 
*Equality results for the conditional mutual information&nbsp; $I(Y; Z \hspace{0.05cm} \vert  \hspace{0.05cm} X) = 0$,&nbsp; i.e. when the random variables&nbsp; $Y$&nbsp; and&nbsp; $Z$&nbsp; for a given&nbsp; $X$&nbsp; are statistically independent.


{{GraueBox|TEXT=
$\text{Example 5:}$&nbsp;  We consider the&nbsp; [[Theory_of_Stochastic_Signals/Markovketten|$\text{Markov chain}$]] &nbsp; $X → Y → Z$.&nbsp; For such a constellation, the&nbsp; "Data Processing Theorem"&nbsp; always holds with the following consequence, which can be derived from the chain rule of mutual information:
 
:$$I(X;Z) \hspace{-0.05cm}  \le  \hspace{-0.05cm}I(X;Y ) \hspace{0.05cm},$$
:$$I(X;Z) \hspace{-0.05cm}  \le  \hspace{-0.05cm} I(Y;Z ) \hspace{0.05cm}.$$

The theorem thus states:
*One cannot gain any additional information about the input&nbsp; $X$&nbsp; by manipulating the data&nbsp; $Y$&nbsp; by processing  &nbsp; $Y → Z$. 
*Data processing&nbsp; $Y → Z$&nbsp; $($by a second processor$)$ only serves the purpose of making the information about&nbsp; $X$&nbsp; more visible.


For more information on the&nbsp; "Data Processing Theorem"&nbsp; see&nbsp; [[Aufgaben:Aufgabe_3.15:_Data_Processing_Theorem|"Exercise 3.15"]].}} 	 


==Exercises for the chapter==
<br> 
[[Aufgaben:Exercise_3.7:_Some_Entropy_Calculations|Exercise 3.7: Some Entropy Calculations]] 

[[Aufgaben:Exercise_3.8:_Once_more_Mutual_Information|Exercise 3.8: Once more Mutual Information]]

[[Aufgaben:Exercise_3.8Z:_Tuples_from_Ternary_Random_Variables|Exercise 3.8Z: Tuples from Ternary Random Variables]]

[[Aufgaben:Exercise_3.9:_Conditional_Mutual_Information|Exercise 3.9: Conditional Mutual Information]]



{{Display}}