Aufgaben:Exercise 3.6: Partitioning Inequality - Revision history

Noah at 08:15, 24 September 2021

2021-09-24T08:15:36Z

Javier: Text replacement - "generalis" to "generaliz"

2021-09-22T11:48:06Z

Text replacement - "generalis" to "generaliz"

Guenter at 15:13, 31 August 2021

2021-08-31T15:13:21Z

Guenter at 14:58, 31 August 2021

2021-08-31T14:58:57Z

Noah at 19:14, 26 August 2021

2021-08-26T19:14:53Z

Show changes

Guenter at 13:34, 16 July 2021

2021-07-16T13:34:33Z

Guenter: Guenter moved page Aufgaben:Aufgabe 3.6: Partitionierungsungleichung to Aufgaben:Exercise 3.6: Partitioning Inequality

2021-07-16T13:27:07Z

Guenter moved page Aufgabe 3.6: Partitionierungsungleichung to Exercise 3.6: Partitioning Inequality

Javier: Text replacement - "Category:Aufgaben zu Informationstheorie" to "Category:Information Theory: Exercises"

2021-03-23T12:45:29Z

Text replacement - "Category:Aufgaben zu Informationstheorie" to "Category:Information Theory: Exercises"

Javier: Text replacement - "[[Informationstheorie" to "[[Information_Theory"

2020-07-09T12:43:01Z

Text replacement - "[[Informationstheorie" to "[[Information_Theory"

Javier: Text replacement - "[[Stochastische_Signaltheorie/" to "[[Theory_of_Stochastic_Signals/"

2020-07-09T09:47:47Z

Text replacement - "[[Stochastische_Signaltheorie/" to "[[Theory_of_Stochastic_Signals/"

← Older revision		Revision as of 08:15, 24 September 2021
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
	}}		}}

@@ Line 128: / Line 128: @@
 :$$\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_1)}{Q_X(B_1)}, \text{ if } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_2)}{Q_X(B_2)}, \text{ if } x \in B_2.$$
-*By generalisation, one can see that&nbsp; <u>both proposed solutions</u>&nbsp; are correct.
+*By generalization, one can see that&nbsp; <u>both proposed solutions</u>&nbsp; are correct.
 {{ML-Fuß}}

@@ Line 84: / Line 84: @@
 {{ML-Kopf}}
-'''(1)'''&nbsp;  For the Kullback-Leibler distance holds:
+'''(1)'''&nbsp;  For the Kullback-Leibler distance of the non-partitioned quantities&nbsp; $X$&nbsp; and&nbsp; $Y$&nbsp; holds:
 :$$D(P_X \hspace{0.05cm} ||  \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{x \hspace{0.05cm}\in \hspace{0.05cm}X}
@@ Line 97: / Line 97: @@
-'''(2)'''&nbsp;  With&nbsp; $\text{partition A}$ &nbsp; &rArr; &nbsp;  $A_1 = \{0\}$ ,&nbsp;  $A_2 = \{ 1 , 2 \}$&nbsp; we get&nbsp;  $P_X^{ (A) } (X) = \{1/4 , \ 3/4\}$&nbsp; and&nbsp; $Q_X^{ (A) } (X) = \{1/8 , \ 7/8\}$.&nbsp;  From this follows:
+'''(2)'''&nbsp;  With&nbsp; $\text{partition }A$ &nbsp; &rArr; &nbsp;  $A_1 = \{0\}$ ,&nbsp;  $A_2 = \{ 1 , 2 \}$&nbsp; we get&nbsp;  $P_X^{ (A) } (X) = \{1/4 , \ 3/4\}$&nbsp; and&nbsp; $Q_X^{ (A) } (X) = \{1/8 , \ 7/8\}$.&nbsp;  From this follows:
 :$$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) = \frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/4}{1/8} +
@@ Line 105: / Line 105: @@
-'''(3)'''&nbsp; With&nbsp; $\text{partition B}$ &nbsp; &rArr; &nbsp;  $B_1 = \{1\}$ ,&nbsp;  $B_2 = \{ 0 ,\ 2 \}$&nbsp; the probability functions are&nbsp;  $P_X^{ (B) } (X) = \{1/2 , \ 1/2\}$&nbsp; und&nbsp; $Q_X^{ (B) } (X) = \{3/4 , \ 1/4\}$.&nbsp;
+'''(3)'''&nbsp; With&nbsp; $\text{partition } B$ &nbsp; &rArr; &nbsp;  $B_1 = \{1\}$ ,&nbsp;  $B_2 = \{ 0 ,\ 2 \}$&nbsp; the probability functions are&nbsp;  $P_X^{ (B) } (X) = \{1/2 , \ 1/2\}$&nbsp; und&nbsp; $Q_X^{ (B) } (X) = \{3/4 , \ 1/4\}$.&nbsp;
 *Analogous to subtask&nbsp; '''(2)'''&nbsp; one thus obtains:
 :$$D(P_X^{\hspace{0.15cm}(B)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(B)})  = \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{3/4} +
 \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{1/4} \hspace{0.15cm} \underline {=0.2075\,{\rm (bit)}}
 \hspace{0.05cm}.$$
-*The result agrees with that of subtask&nbsp; '''(1)'''&nbsp; &nbsp; &rArr; &nbsp; With&nbsp; $\text{partition B}$&nbsp; the equal sign applies.
+*The result agrees with that of subtask&nbsp; '''(1)'''&nbsp; &nbsp; &rArr; &nbsp; With&nbsp; $\text{partition }B$&nbsp; the equal sign applies.
-'''(4)'''&nbsp; With&nbsp; $\text{partition C}$ &nbsp; &rArr; &nbsp;  $C_1 = \{2\}$ ,  $C_2 = \{ 0 , \ 1\}$&nbsp; one obtains&nbsp;  $P_X^{ (C) } (X) = \{1/4, \  3/4\}$  , $Q_X^{ (C) } (X) = \{1/8, \ 7/8\}$, <br>i.e. the same functions as for the&nbsp; $\text{partition A}$ &nbsp; &rArr; &nbsp; <u>solution proposal 1</u>.
+'''(4)'''&nbsp; With&nbsp; $\text{partition } C$ &nbsp; &rArr; &nbsp;  $C_1 = \{2\}$ ,  $C_2 = \{ 0 , \ 1\}$&nbsp; one obtains&nbsp;  $P_X^{ (C) } (X) = \{1/4, \  3/4\}$  , $Q_X^{ (C) } (X) = \{1/8, \ 7/8\}$, <br>i.e. the same functions as for the&nbsp; $\text{partition }A$ &nbsp; &rArr; &nbsp; <u>solution proposal 1</u>.
-'''(5)'''&nbsp; The&nbsp; $\text{partition C}$&nbsp; has led to the result&nbsp; $D(P_X^{ (B) } \hspace{0.05cm} ||  \hspace{0.05cm}Q_X^{ (B) } ) = D(P_X \hspace{0.05cm} ||  \hspace{0.05cm}Q_X)$ geführt.
+'''(5)'''&nbsp; The&nbsp; $\text{partition }B$&nbsp; has led to the result&nbsp; $D(P_X^{ (B) } \hspace{0.05cm} ||  \hspace{0.05cm}Q_X^{ (B) } ) = D(P_X \hspace{0.05cm} ||  \hspace{0.05cm}Q_X)$.
 *So for this case
 :$$\frac{P_X(1)}{Q_X(1)} =  \frac{1/2}{3/4} = \frac{2}{3},  \ \frac{P_X(B_1)}{Q_X(B_1)} = \frac{1/2}{3/4} = {2}/{3},$$
@@ Line 126: / Line 126: @@
 *It must therefore hold for all&nbsp; $x \in X$&nbsp; :
-:$$\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_1)}{Q_X(B_1)}, \text{falls } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_2)}{Q_X(B_2)}, \text{falls } x \in B_2.$$
+:$$\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_1)}{Q_X(B_1)}, \text{ if } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)}  = \frac{P_X(B_2)}{Q_X(B_2)}, \text{ if } x \in B_2.$$
 *By generalisation, one can see that&nbsp; <u>both proposed solutions</u>&nbsp; are correct.

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2812__Inf_A_3_5.png|right|frame|Probability functions&nbsp; $P_X$,&nbsp; $Q_X$]]
+[[File:P_ID2812__Inf_A_3_5.png|right|frame|Two probability functions&nbsp; $P_X$&nbsp; and&nbsp; $Q_X$]]
-The&nbsp; ''Kullback–Leibler distance''&nbsp; (KLD for short) is also used in the ''Partition Unequality'':
+The&nbsp; '''Kullback–Leibler distance'''&nbsp; (KLD for short)&nbsp; is also used in the&nbsp;  "Partition Unequality":
 * We assume the set&nbsp; $X =  \{ x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M   \}$&nbsp; and the probability functions
 :$$P_X(X) = P_X (  x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M   )\hspace{0.05cm},$$
 :$$Q_X(X) =Q_X (  x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M   ), $$
-:which are said to be "similar in some way".
+:which are said to be&nbsp; "similar in some way".
 * We divide the set&nbsp; $X$&nbsp; into partitions&nbsp; $A_1, \text{...} ,&nbsp; A_K$, which are&nbsp; [[Theory_of_Stochastic_Signals/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjoint]]&nbsp; to each other and result in a&nbsp; [[Theory_of_Stochastic_Signals/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|complete system]]&nbsp;:
@@ Line 14: / Line 14: @@
 * In the following, we denote the probability functions with respect to the partitionings&nbsp; $A_1,\ A_2, \text{...} ,\ A_K$&nbsp; by
-:$$P_X^{\hspace{0.15cm}(A)} = \big [ P_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},P_X (  A_K  ) \big  ],\hspace{0.05cm}\hspace{0.5cm}{\rm wobei}\hspace{0.15cm} P_X (  A_i  ) = \sum_{ x \in A_i} P_X ( x  )\hspace{0.05cm},$$
+:$$P_X^{\hspace{0.15cm}(A)} = \big [ P_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},P_X (  A_K  ) \big  ],\hspace{0.05cm}\hspace{0.5cm}{\rm where}\hspace{0.15cm} P_X (  A_i  ) = \sum_{ x \in A_i} P_X ( x  )\hspace{0.05cm},$$
-:$$Q_X^{\hspace{0.15cm}(A)}= \big  [ Q_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},Q_X (  A_K  ) \big  ],\hspace{0.05cm}\hspace{0.40cm}{\rm wobei}\hspace{0.15cm} Q_X (  A_i  ) = \sum_{ x \in A_i} Q_X ( x  )\hspace{0.05cm}. $$
+:$$Q_X^{\hspace{0.15cm}(A)}= \big  [ Q_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},Q_X (  A_K  ) \big  ],\hspace{0.05cm}\hspace{0.40cm}{\rm where}\hspace{0.15cm} Q_X (  A_i  ) = \sum_{ x \in A_i} Q_X ( x  )\hspace{0.05cm}. $$
 {{BlaueBox|TEXT=
@@ Line 23: / Line 23: @@
-In subtask&nbsp; '''(1)'''&nbsp; the Kullback-Leibler distance of the two probability functions&nbsp; $P_X(X)$&nbsp; and&nbsp; $Q_X(X)$&nbsp; for&nbsp; $X = \{0,\ 1,\ 2\}$ &nbsp; &rArr; &nbsp; $|X| = 3$ is to be determined.
+In subtask&nbsp; '''(1)'''&nbsp; the Kullback-Leibler distance of the two probability functions&nbsp; $P_X(X)$&nbsp; and&nbsp; $Q_X(X)$&nbsp; for&nbsp; $X = \{0,\ 1,\ 2\}$ &nbsp; &rArr; &nbsp; $|X| = 3$&nbsp; is to be determined.
-*Then the setnbsp; $X$&nbsp; is to be partitioned with&nbsp; $K = 2$&nbsp; according to
+*Then the set&nbsp; $X$&nbsp; is to be partitioned with&nbsp; $K = 2$&nbsp; according to
 :* $A = \{A_1 ,\ A_2\}$&nbsp;   with&nbsp;  $A_1 =\{0\}$&nbsp;  and&nbsp; $A_2 = \{ 1,\ 2 \}$ ,
 :* $B = \{B_1 ,\ B_2\}$&nbsp;   with&nbsp;  $B_1 =\{1\}$&nbsp;  and&nbsp; $B_2 = \{ 0,\ 2 \}$,
-:* $C = \{C_1 ,\ C_2\}$&nbsp;   with&nbsp;  $C_1 =\{2\}$&nbsp;  and&nbsp; $C_2 = \{  0,\ 1\}$,
+:* $C = \{C_1 ,\ C_2\}$&nbsp;   with&nbsp;  $C_1 =\{2\}$&nbsp;  and&nbsp; $C_2 = \{  0,\ 1\}$.
 *Then the respective Kullback-Leibler distances are to be given:
@@ Line 46: / Line 46: @@
 Hints:
-*The task belongs to the chapter&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Some preliminary remarks on 2D random variables]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Some_Preliminary_Remarks_on_Two-Dimensional_Random_Variables|Some preliminary remarks on two-dimensional random variables]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Informational_divergence_-_Kullback-Leibler_distance|Informational Divergence &ndash; Kullback-Leibler distance]].
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Some_Preliminary_Remarks_on_Two-Dimensional_Random_Variables#Informational_divergence_-_Kullback-Leibler_distance|Relative entropy &ndash; Kullback-Leibler distance]].
 *The two probability functions can be read from the above graph as follows:
 :$$P_X(X) = \big [1/4 , \ 1/2 , \ 1/4 \big ],\hspace{0.5cm} Q_X(X) = \big [1/8, \ 3/4, \ 1/8 \big].$$
@@ Line 57: / Line 56: @@
 <quiz display=simple>
-{Calculate the Kullback-Leibler distance (KLD) in general.
+{Calculate the Kullback-Leibler distance in general.
 |type="{}"}
 $ D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm}  Q_X) \ = \ $ { 0.2075 3% } $\ \rm bit$
-{WWhat is the Kullback-Leibler distance for the partition&nbsp;  $ A_1 = \{0\},\ A_2 = \{1, 2\}$?
+{What is the Kullback-Leibler distance for the partition&nbsp;  $ A_1 = \{0\},\ A_2 = \{1, 2\}$?
 |type="{}"}
 $D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } ) \ = \ $ { 0.0832 3% } $\ \rm bit$
@@ Line 71: / Line 70: @@
 {What is the Kullback-Leibler distance for the partition&nbsp;  $ C_1 = \{2\},\ C_2 = \{0, 1\}$?
 |type="()"}
-+ The same result as for partition&nbsp; $A$.
++ The same result as for partition&nbsp; $\rm A$.
-- The same result as for partition&nbsp; $B$.
+- The same result as for partition&nbsp; $\rm B$.
 - A completely different result.
-{Under which conditions does equality result for genera&nbsp; $K$&nbsp;?
+{Under which conditions does equality result for general&nbsp; $K$&nbsp;?
 |type="[]"}
 + &nbsp; $|X|$&nbsp; equations must be fulfilled.

← Older revision		Revision as of 13:34, 16 July 2021
Line 135:		Line 135:


−	[[Category:Information Theory: Exercises \|^3.1 ~~Allgemeines zu~~ 2D~~-Zufallsgrößen~~^]]	+	[[Category:Information Theory: Exercises \|^3.1 General Information on 2D Random Variables^]]

← Older revision		Revision as of 12:45, 23 March 2021
Line 135:		Line 135:


−	[[Category:~~Aufgaben zu Informationstheorie~~ \|^3.1 Allgemeines zu 2D-Zufallsgrößen^]]	+	[[Category:Information Theory: Exercises \|^3.1 Allgemeines zu 2D-Zufallsgrößen^]]

@@ Line 46: / Line 46: @@
 ''Hinweise:''
-*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
+*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
-*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Relative_Entropie_.E2.80.93_Kullback.E2.80.93Leibler.E2.80.93Distanz|Relative Entropie &ndash; Kullback-Leibler-Distanz]].
+*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Relative_Entropie_.E2.80.93_Kullback.E2.80.93Leibler.E2.80.93Distanz|Relative Entropie &ndash; Kullback-Leibler-Distanz]].
 *Die beiden  Wahrscheinlichkeitsfunktionen können aus obiger Grafik wie folgt abgelesen werden:

@@ Line 10: / Line 10: @@
 :aus, die „in irgendeiner Form ähnlich” sein sollen.
-* Die Menge&nbsp; $X$&nbsp; unterteilen wir in die Partitionen&nbsp; $A_1, \text{...} ,&nbsp; A_K$, die zueinander&nbsp; [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjunkt]]&nbsp; sind und ein&nbsp; [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|vollständiges System]]&nbsp; ergeben:
+* Die Menge&nbsp; $X$&nbsp; unterteilen wir in die Partitionen&nbsp; $A_1, \text{...} ,&nbsp; A_K$, die zueinander&nbsp; [[Theory_of_Stochastic_Signals/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjunkt]]&nbsp; sind und ein&nbsp; [[Theory_of_Stochastic_Signals/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|vollständiges System]]&nbsp; ergeben:
 :$$\bigcup_{i=1}^{K} = X, \hspace{0.5cm} A_i \cap A_j = {\it \phi} \hspace{0.25cm}\text{für}\hspace{0.25cm} 1 \le i \ne j \le K .$$