Information Theory: A Constructive Crash Course

This text aims at intuitively explaining and proving the main definitions and theorems of Shannon's information theory with limited prerequisites; this includes: cross/conditional entropy, KL-divergence, mutual information, asymptotic codelength property (variant of AEP), source and channel coding theorems. It contains a new constructive proof of the coding theorem for discrete memoryless channel and an other non constructive proof of achievability of Shannon's capacity for the bit-flip channel.

The target audience is "undergraduates/good high school students" but anyone is welcome here.

Find the coin

As a playful formalist, I would like to introduce the subject with a small game. ;)

A coin is hidden among four opaque cups. At each round, we ask yes/no questions to uncover the cup concealing the coin. Multiple rounds are played and we aim to minimize the number of questions asked.

We first assume the coin has $1$ in $4$ chances to be under each cup such that the best strategy is a binary search asking $2$ questions per round.

But after playing a few rounds, we notice the coin has in fact $1$ in $2$ chance to be in the first cup, $1$ in $4$ to be in the last one and $1$ in $8$ to be in the others. If we update our questionnaire asking: "Is the coin in the first cup? Is the coin in the last cup? Is the coin in this remaining cup?” we will ask on average only $\frac{1}{2}+\frac{1}{4}\times2+\left(\frac{1}{8}+\frac{1}{8}\right)\times3=1.75$ questions per round.

Now imagine playing the same game using only two cups with a $70\%$ chance for the coin to be in the first cup and $30\%$ chance to be in the other. Here, we must ask one question per round.

But let's change the rules of the game allowing questions relative to two simultaneous rounds. There is a $49\%$ chance for the two coins to be in their first cups, $9\%$ chance for them to be in their last cups and $21\%$ for the two other cases. The best strategy will ask $\frac{1}{2}(0.49+0.21\times2+(0.21+0.09)\times3)=0.905$ questions per coin.

Entropies and KL divergence

Given $n$ cups and their probabilities to contain the coin $p_{1},\dots,p_{n}$, as we increase the number of simultaneous rounds, the number of questions per coin of the best strategy will converge to,

where $\log_{2}$ is the binary logarithm.

This is the entropy of the distribution $p$ and is denoted $H(p)$. If a single-round optimal strategy exists, we can view it as a decision tree: $-\log_{2}\left(p_{i}\right)$ is the length of the branch we will follow with probability $p_{i}$ when the coin is found in the $i_{^{th}}$ cup.

Now if we assume the wrong distribution $q$, the number of questions we ask on average is:

This is the cross-entropy $H(p,q)$ and it is not symmetric. As expected:

The difference is called Kullback-Leibler divergence, we note:

In the rest of the text we will drop the $2$ from $\log_{2}$ for simplicity.

Conditional entropies

Let $X$ and $Y$ be two discrete random variables, we will write the conditional probabilities as,

hence,

and the expected value operator being linear,

we will note,

and:

With a similar reasonning, given $X_{1},\dots,X_{n}$ discrete random variables:

Mutual information

Given two discrete random variables $X$ and $Y$ we have, $H(X)+H(Y)-H(XY)=D_{KL}(P(X,Y)\Vert P(X)\otimes P(Y))\geq 0$ where $\otimes$ denotes the outer product.

This quantity is called the mutual information $I(X, Y)$.

It can be equivalently expressed as:

This is left as an exercise but rest assured from that point on we will prove everything.

Source coding theorem (lower bound)

For a discrete random variable $X$, a binary encoding $b$ of $X$ is an injection from the domain of $X$ to the set of binary strings. Noting $B_X=b(X)$ and $B_{X}^{i}$ the binary random variable given by the $i_{^{th}}$ bit when the length $\overline{B_X} \geqslant i$. For a such binary encoding we have:

Indeed, since $b$ is injective we get:

Using the fact that for any $B$ binary random variable $H(B)\leq 1$.

Source coding theorem (upper bound)

Given $\epsilon>0$ and $n>1$, noting $X^n$ a sequence of $n$ random variables from a same distribution, there exists a binary encoding $B_{X^n}$ such that:

From the conditional entropy formula we have $H(X^{n})=nH(X)$, so the left inequality is given by our previous result.

For the right hand side, we first notice that given some naturals $l_{1}\leq\dots\leq l_{n}$ where $\sum2^{-l_{i}}\leq1$ we can build binary strings of lengths $l_{1},\dots,l_{n}$ such that no string is the prefix of another.

Indeed, $1-\sum2^{-l_i}$ is a multiple of $2^{-l_n}$, such that adding $2^{l_{n}}-\sum2^{l_{n}-l_{i}}$ times $l_{n}$ to our set of lengths we get $\sum 2^{-l_i} = 1$. Then, if we prune an infinite binary tree at these lengths, the set of paths from the root to the leafs described using left/right instructions will form a valid prefix-distinct set of binary strings.

Now if we pick the lengths as $\left\lceil -\log_{2}P(X^{n}=(x_{1},\dots,x_{n}))\right\rceil$ then:

And we obtain the right inequality for $n>1/\epsilon$.

Asymptotic Codelength Property (ACP)

Given $n > 1$, some sequence of $n$ discrete random variables $X^n$ and some logical statement $S({X^n})$, we will say that $S(X^n)$ holds almost surely asymptotically (a.s.a.) if we have:

Let $m > 1$, using previous notation, we can encode $X^{nm} =(X^n_{1},\dots,X^n_{m})$ as $B_{X^{nm}}=B_{X^n_1}\dots B_{X^n_m}$ since the encoding $B_{X^n}$ is prefix-distinct.

With the weak law of large numbers we get a.s.a.,

using the last inequality of the previous section and $\mathbb{E}[\overline{B_{X^{n}}}]\geqslant nH(X)$ a.s.a.,

and with $n=m$ and $k=n^2$, using Landau's notation we get a.s.a.:

Given a sequence of $k$ discrete random variables $Y^k$ sampled from a conditional distribution $P(Y=y|X=x)$ we can similarly consider of the conditional encoding $B_{Y^k|X^k=x^k}$.

With the weak law of large number we have a.s.a. $H(Y^k|X^k=x^k)\in [kH(Y|X)\pm o(k)]$. Pairing this result with the above construction we get a.s.a. $\overline{B_{Y^k|X^k=x^k}} \in \left[kH(Y|X)\pm o(k)\right]$.

Prefix tree rebalancing

$B_{Y^{k}|X^{k}=x^k}$ is a prefix distinct encoding as concatenation of prefix distinct encodings.

Given $\epsilon > 0$, we can then perform a rebalacing of the prefix distinct tree defining $B_{Y^{k}|X^{k}=x^k}$ as follow:

1. if $\overline{B_{Y^{k}|X^{k}=x^k}(y^n)}<k(H(Y|X) - \epsilon)$ pad it with ones to length $k(H(Y|X) - \epsilon)$
2. use the new internal nodes with a single child to graft branches pruned from length $k(H(Y|X) - \epsilon)$

We repeat these two operations till the level $k(H(Y|X) - \epsilon)$ of the binary tree is "full" or there is no branch left to prune.

We can bound the increase in expected length from the padding step by $P(\overline{B_{Y^{k}|X^{k}=x^k}(y^n)}<k(H(Y|X) - \epsilon))H(X|Y)k=|o(k)|$, and the grafting step followed by the second padding step only decrease the expected length (inductively for following iterations).

For large enough $k$, the rebalancing procedure terminates with a full $k(H(Y|X) - \epsilon)$ level since a.s.a. $H(B_{Y^{k}|X^{k}=x^k}) = H(Y^k|X^k=x^k) \in [kH(Y|X) \pm o(k)]$. Let's pick such $k$.

Since this is valid for any $\epsilon > 0$ we can pick a suitable $o(k)$ such that $\epsilon = |o(k)|/k$.

Unification of prefix encodings using branch permutations

After the rebalancing we can view the prefix from $B_{Y^{k}|X^{k}=x^k}$ of length $kH(Y|X) - |o(k)|$ as defining a family of surjections indexed by $x^k$ from the domain of $Y^k$ to binary strings of said length.

We can then consider the right inverses $f_{x^k}$ (note we don't need the axiom of choice since all sets are finite) such that $\text{prefix}_{kH(Y|X) - o(k)}(B_{Y^{k}|X^{k}=x^k})\circ f_{x^k}=B_{Y^k|X^k}$.

Note that $B_{Y^k|X^k}$ is a function of $y^k$ that does not depend upon the realisation $x^k$ of $X^k$. Using $H(B_{Y^k|X^k=x^k})\in [kH(Y|X)\pm o(k)]$ we have $H(B_{Y^k|X^k}) = kH(Y|X)-|o(k)|$.

Similarly, the suffix $B'_{Y^k|X^k=x^k}$ has an entropy of $|o(k)|$. We are now ready to dive into the channel coding theorem.

Channel capacity

A communication channel is modeled by a source of input messages $X$ transmitted and received as output messages $Y$ on the other end of the channel. The conditional distribution $P(Y|X)$ defines the reliability of the channel.

Given a fixed conditional distribution $P(Y|X)$, we can try to modify the distribution of the input messages $P(X)$ to maximize the mutual information $I(X,Y)$. This maximal mutual information is called the capacity of the channel.

Channel coding theorem

Given $n$ pairs of discrete random variables sampled from a joint probability distribution, we note $X^n$ and $Y^n$ the deinterlaced sequences.

Let $(e_n)$ and $(d_n)$ be sequences of functions such that $H(e_n(X^n)|d_n(Y^n))=|o(n)|$ and $H(d_n(Y^n)|e_n(X^n))=|o(n)|$. If we note,

then:

Channel coding proof (achievability)

For the rest of the proof we will note $C=I(X,Y)$ and $n>1$.

We first remark we can encode $(X^n, Y^n)$ in two ways:

• $B_{X^n|Y^n}B_{X^n|B_{X^n|Y^n}}B_{Y^n|X^n}B'_{X}$
• $B_{Y^n|X^n}B_{Y^n|B_{Y^n|X^n}}B_{X^n|Y^n}B'_{Y}$

with $H(B'_{X})=|o(n)|$ and $H(B'_{Y})=|o(n)|$ as concatenations of various suffixes.

Droping $B_{X^n|Y^n}$ and $B_{Y^n|X^n}$ we notice,

that is $H(B_{Y^n|B_{Y^n|X^n}}B'_{Y}|B_{X^n|B_{X^n|Y^n}})=|o(n)|$ and droping $B'_{Y}$ we have,

and similarly:

Furthermore we have $H(B_{Y^n|B_{Y^n|X^n}}) = nC - |o(n)|$ and $H(B_{X^n|B_{X^n|Y^n}}) = nC - |o(n)|$.

Channel coding proof (optimality)

By contradiction, using Landau's notation, let's assume there is a $d_n$ such that,

Since $H(X^nY^n)=H(X^n)+H(B_{Y^n|X^n})+o(n)$, we would have,

but since:

Contradiction.

Bonus 1: capacity of the bit flip channel

Inputs and outputs of this channel take binary values and the conditional probabilities are,

• $P(Y=0|X=1)=p$
• $P(Y=1|X=0)=p$

where $0\leq p\lt \frac{1}{2}$ and the two missing conditional probabilities can be deduced.

We can bound the mutual information:

And the bound is reached when $P(Y=0)=1/2$ that is when $P(X=0)=1/2$.

From now on, we will note $h(p)=-p\log_{2}p-(1-p)\log_{2}(1-p)$.

Bonus 2: proof of achivability for the bit flip channel

The idea of the proof consists in taking a random set of binary strings of given length $n$ and to show that if this set contains less than $2^{n(C-\epsilon)}$ strings, for any $\epsilon>0$, we will be almost certain to recognize the strings after a transmission as $n$ goes to infinity.

Let's assume $\eta>0$ is our targeted probability of error. If we transmit a random string of length $n$ chosen among a set of size $2^{nR}$, the number of bit flips $F$ will follow a binomial distribution with parameters $n$ and $p$.

With Chebyshev's inequality we get:

Let's pick $k$ such that $1/k^{2}<\eta/2$.

Now assuming $|F-np|\lt k\sqrt{p(1-p)n}$, we must find a condition on $R$ such that the probability of having an other transmitted string in a radius of $np+k\sqrt{p(1-p)n}$ flips is lower than $\eta/2$.

Since the set of strings is chosen uniformly at random, the number of flips $F'$ from the original transmitted string to any other transmitted string will follow a binomial distribution of parameters $n$ and $1/2$. So we need:

Using the fact that for $n>1$, $1-(1-x)^{n}$ is below its tangent $nx$ at $0$:

Indeed, since $p<1/2$ for $n$ large enough, we have for all $i\lt np+o(n)$:

Now, as a small interlude, let's prove for $k\leq n$, $\binom{n}{k}\leq2^{nh\left(\frac{k}{n}\right)}$:

For our main inequality, we get,

and if $R<1-h(p)=C$, the probability $p_{error}$ goes to $0$ as desired.