01.4 Conditional Entropy

The idea is to pack a lot of symbols into supersymbols $(S_1,S_2,S_3,\dots ,S_n)$

Theorem

The average codeword-length of a uniquely decodable code $\Gamma$ for $S$ must satisfy :

$$H_D(S_1,S_2,\dots ,S_n)\le L((S_1,S_2,\dots ,S_n),\Gamma )$$

And there exists a uniquely decodable code ${\Gamma }_{SF}$ satisfying

$$L((S_1,S_2,\dots ,S_n),{\Gamma }_{SF})<H_D(S_1,S_2,\dots ,S_n)+1$$

(By joint entropy)

Let’s understand $H_D(S_1,S_2,\dots ,S_n)$, for that we need to

• understand conditional entropy
• understand how to model many random variables

Conditional Probability

Definition (coin flip source)

The source models a sequence $S_1,S_2,\dots ,S_n$ So $S_i\in \mathcal{A}=\{H,T\}$, with $H$ is heads and $T$ is tails $p_{S_i}(H)=p_{S_i}(T)=\frac{1}{2}$ for all $i$ Hence

$$p_{S_1,S_2,\dots ,S_n}(s_1,s_2,\dots ,s_n)=\frac{1}{2^n}$$

Definition (Sunny-Rainy Source)

The source models a sequence $S_1,S_2,\dots ,S_n$ So $S_i\in \mathcal{A}=\{S,R\}$, with $S$ being sunny weather and $R$ being rainy weather The weather is uniformly distributed in $\mathcal{A}$ For all other days, the weather stays the same with probability $\frac{6}{7}$

As we have seen conditional probability, I won’t re-explain it.

Conditional Expectation of $X$ given $Y=y$

Definition

The conditional expectation of $X$ given $Y=y$ is defined as

$$\mathbb{E}[X|Y=y]=\sum _{x\in X}x{p}_{X|Y}(x|y)$$

We have every probability associated to an entropy

• $p_X(\cdot )\mapsto H(X)$
• $p_{X\mid Y}(\cdot \mid y)\mapsto H(X\mid Y=y)$

Definition

The conditional entropy of $X$ given $Y=y$ is defined as

$$H_D(X\mid Y=y)=-\sum _{x\in X}{p}_{X\mid Y}(x\mid y){\log }_D{p}_{X\mid Y}(x\mid y)$$

Theorem

The conditional entropy of a discrete random variable $X\in \mathcal{X}$ knowing $Y=y$

$$0\le H_D(X\mid Y=y)\le {\log }_D|\mathcal{X}|$$

with equality on the left $⟺p_{X\mid Y}(x\mid y)=1$ for some $x$, and with equality on the right $⟺p_{X\mid Y}(x\mid y)=\frac{1}{|\mathcal{X}|}$ for all $x$

However conditional entropy is not bounded by the entropy of its random variable

$$H_D(X\mid Y=y)\nleqq H_D(X)$$

You might find a 100 papers in a machine learning course that say that this inequality holds, but that's because they don't like doing real work

Definition

The conditional entropy of $X$ given $Y$ is defined as

$$H_D(X\mid Y)=\sum _{y\in Y}{p}_Y(y)\left(-\sum _{x\in X}{p}_{X\mid Y}(x\mid y){\log }_D{p}_{X\mid Y}(x\mid y)\right)$$

Theorem

The conditional entropy of a discrete random variable $X\in \mathcal{X}$ given $Y$

$$0\le H_D(X\mid Y)\le {\log }_D|\mathcal{X}|$$

with equality on the left $⟺p_{X\mid Y}(x\mid y)=1$ for every $y$ for some $x$, and with equality on the right $⟺p_{X\mid Y}(x\mid y)=\frac{1}{|\mathcal{X}|}$ for all $x$ and all $y$

Conditioning reduces entropy

Theorem

For any two discrete random variables $X$ and $Y$,

$$H_D(X\mid Y)\le H_D(X)$$

with equality $⟺$ $X$ and $Y$ are independent

(Makes sense because if $Y$ gives no information about the state of $X$, why would it affect its entropy) On average, the uncertainty of $X$ can only become smaller if we know $Y$

Theorem

For any three discrete random variables $X$, $Y$ and $Z$

$$H_D(X\mid Y,Z)\le H_D(X\mid Z)$$

with equality $⟺$ $X$ and $Y$ are conditionally independent random variables

Chain Rule for Entropy

We can rewrite as

$$H_D(X,Y)=H_D(X)+H_D(Y\mid X)$$

Or, in english, to find the joint entropy of two random variables, we can first calculate the entropy of one of the two, and add the conditional entropy of the second given the first.

→ We can chain this a bunch of times (hence the name)

Theorem

Let $S_1,\dots ,S_n$ be discrete random variables. Then

$$H_D(S_1,S_2,\dots ,S_n)=H_D(S_1)+H_D(S_2\mid S_1)+\cdots +H_D(S_n\mid S_1,S_2,\dots ,S_{n-1})$$

Infinite alphabet prefix-free code

Let’s do an example with integers

The binary expansion of the number is not prefix free. Therefore it is not desirable.

Elias Code

What if we prefix the binary expansion with $l(n)-1$ zeros? The code is prefix-free, but it is rather long: $l_1(n)=l(n)-1+l(n)=2\lfloor {\log }_{2}n\rfloor +1$ → This is not optimal

Elias Code 2

We prefix with elias code of the length of the binary expansion.