Information Theory Crash Course

Let’s start with a game.

A coin is hidden among four opaque cups. At each round, we ask yes/no questions to uncover the cup containing 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. The best strategy is then a binary search asking $2$ questions per round.

Suppose we notice the coin has in fact $1$ in $2$ chances to be in the first cup, $1$ in $4$ to be in the last one and $1$ in $8$ to be in the others. Using the questionnaire “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.

Imagine now 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.

Entropy 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,
$$-\sum_{i=1}^{n}p_{i}\log_{2}\left(p_{i}\right)$$

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:
$$-\sum_{i=1}^{n}p_{i}\log_{2}\left(q_{i}\right)$$

This is the cross-entropy $H(p,q)$. As expected:
$$H(p,q) \geq H(p)$$

The difference is called Kullback-Leibler divergence and we note:
$$D_{KL}(p\Vert q)=H(p,q)-H(p)$$

Conditional entropy

Let $X$ and $Y$ be two discrete random variables, using conditional probabilities we get,
$$P(X,Y)=P(X)P(Y|X)$$

hence,
$$\log_{2}P(X,Y)=\log_{2}P(X)+\log_{2}P(Y|X)$$

and the expected value operator being linear,
$$\mathbb{E}\left[\log_{2}P(X,Y)\right]=\mathbb{E}\left[\log_{2}P(X)\right]+\mathbb{E}\left[\log_{2}P(Y|X)\right]$$

we will note:
$$H(XY)=H(X)+H(\pi_X(Y))$$

$\pi_X(Y)$ can be interpreted as a random variable obtained from $Y$ once $X$ has been realized.

Similarly, given $X_{1},\dots,X_{n}$ discrete random variables:
$$H(X_{1}\dots X_{n})=\sum_{i=1}^{n}H\left(\pi_{X_{j\lt i}}\left(X_{i}\right)\right)$$

Note that $H(X)+H(Y)-H(XY)=D_{KL}(P(X,Y)\Vert P(X)\otimes P(Y))\geq 0$ where $\otimes$ denotes the tensor product.

This is $0$ if and only if $X$ and $Y$ are independent, hence:
$$H(XY)\geq H(X\pi_X(Y)) \leq H(X) + H(\pi_X(Y))=H(XY)$$

The above formula is then an equality proving that $X$ and $\pi_X(Y)$ are independent.

Source coding theorem (lower bound)

For a discrete random variable $X$, a binary encoding $b$ of $X$ is an injective function from the domain of $X$ to the set of binary strings. Noting $B_X=b(X)$ and $B_{i}$ the binary variable given by the $i_{^{th}}$ bit when the length $\left\Vert B_X\right\Vert \geqslant i$. For a suchll binary encoding we have:
$$\mathbb{E}[\left\Vert B_X\right\Vert ]\geqslant H(X)$$

Indeed, since $b$ is injective we get:
$$\begin{align*} H(X) & =H(B_X)\\ & =\sum_{i=1}^{\max\left\Vert b\right\Vert }P(\left\Vert B_X\right\Vert =i)H(\pi_{\left\Vert B_X\right\Vert =i}(B_X))\\ & =\sum_{i=1}^{\max\left\Vert b\right\Vert }P(\left\Vert B_X\right\Vert =i)\sum_{j=1}^{i}H\left(\pi_{\left\Vert B_X\right\Vert =i}\left(\pi_{B_{k\lt j}}\left(B_{j}\right)\right)\right)\\ & \leq\sum_{i=1}^{\max\left\Vert b\right\Vert }P(\left\Vert B_X\right\Vert =i)\times i\\ & \leq\mathbb{E}[\left\Vert B_X\right\Vert ] \end{align*}$$

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:
$$nH(X)\leq\mathbb{E}\left[\left\Vert B_{X^n}\right\Vert \right]\leq n\left(H(X)+\epsilon\right)$$

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 will first show 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, we notice that $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:
$$\begin{align*} \mathbb{E}\left[\left\Vert B_{X^n}\right\Vert \right] & =\sum P(X^{n}=(x_{1},\dots,x_{n}))\left\lceil -\log_{2}P(X^{n}=(x_{1},\dots,x_{n}))\right\rceil \\ & \leq\sum P(X^{n}=(x_{1},\dots,x_{n}))(1-\log_{2}P(X^{n}=(x_{1},\dots,x_{n})))\\ & \leq n\left(H(X)+\frac{1}{n}\right) \end{align*}$$

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

Asymptotic codelength property

Reusing previous notations, we have:
$$0\leq\mathbb{E}\left[\left\Vert B_{X^n}\right\Vert \right]-nH(X)\leq 1$$

Let’s denote this quantity $\theta$ and $\epsilon = \theta/n$. Given $m$ a multiple of $n$ and encoding $X^m$ as concatenations of $X^n$ encodings, Chebyshev’s inequality gives,
$$P(|\left\Vert B_{X^m}\right\Vert - mH(X)- \epsilon m|>\sqrt{\frac{m}{\delta}}\sigma_n))<\delta$$

for any $\delta > 0$, with $\sigma_n^2$ the variance of $\left\Vert B_{X^n}\right\Vert$.

Then using the triangle inequality we get,
$$P(|\left\Vert B_{X^m}\right\Vert - mH(X)|> \epsilon m+\sqrt{\frac{m}{\delta}}\sigma_n))<\delta$$

and finally, with Landau’s notation:
$$P(|\left\Vert B_{X^m}\right\Vert - mH(X)|>\epsilon m+o(m))<\delta$$

Mutual information and channel capacity

Given two discrete random variables $X$ and $Y$ we note,
$$I(X,Y)=H(X)+H(Y)-H(XY)$$

the mutual information between $X$ and $Y$.

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 probability $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 a joint probability distribution with mutual information $C$ and $X^n,Y^n$ sequences of $n$ random variables sampled from it, there exist two sequences of functions $(e_n)$ and $(d_n)$ such that,
$$\lim_{n\to\infty}P(e_n(X^n)=d_n(Y^n))=1$$

and, using Landau’s notation:
$$H(e_n(X^n))=nC+o(n)=H(d_n(Y^n))$$

Conversely, if
$$H(e_n(X^n))=nC+|\Omega(n)|=H(d_n(Y^n))$$

and the above limit exists, then it cannot be $1$.

Bit flip channel (capacity)

Before proving the theorem in a more general setting and to make things concrete, let’s look at an example: 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:
$$\begin{align*} I(X,Y) & =-H(Y|X)+H(Y)\\ & =p\log_{2}p+(1-p)\log_{2}(1-p)+H(Y)\\ & \leq p\log_{2}p+(1-p)\log_{2}(1-p)+1 \end{align*}$$

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)$.

Since we now have the capacity of the bit flip channel, we can try to prove the first half of the channel coding theorem in this specific case.

Bit flip channel (channel coding theorem)

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:
$$P\left(|F-np|\geq k\sqrt{p(1-p)n})\right)\leq\frac{1}{k^{2}}$$

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:
$$p_{error}=1-\left(1-P\left(F'\lt np+k\sqrt{p(1-p)n}\right)\right)^{2^{nR}-1}\leq\frac{\eta}{2}$$

Using the fact that for $n>1$, $1-(1-x)^{n}$ is below its tangent $nx$ at $0$:
$$\begin{align*} p_{error} & \leq(2^{nR}-1)\times P\left(F'\lt np+k\sqrt{p(1-p)n}\right)\\ & \leq(2^{nR}-1)\times\sum_{i=0}^{np+o(n)}\binom{n}{i}2^{-n}\\ & \leq2^{n(R-1)}\sum_{i=0}^{np+o(n)}\binom{n}{i}\\ & \leq2^{n(R-1)}(np+o(n))\binom{n}{np+o(n)} \end{align*}$$

Now, as a small interlude, let’s prove for $k\leq n$, $\binom{n}{k}\leq2^{nh\left(\frac{k}{n}\right)}$:
$$\begin{align*} \left(\frac{k}{n}+1-\frac{k}{n}\right)^{n} & =1\\ \binom{n}{k}\left(\frac{k}{n}\right)^{k}\left(1-\frac{k}{n}\right)^{n-k} & \leq1\\ \binom{n}{k} & \leq2^{nh\left(\frac{k}{n}\right)} \end{align*}$$

For our main inequality, we get,
$$p_{error} \leq2^{n(R-1)}(np+o(n))2^{nh(p+o(1))}$$

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

Proof of the channel coding theorem (first half)

Given $n\gt 0$, we have,

$$\begin{align*}H(X^{n}Y^{n}) & =H(\pi_{Y^n}(X^n))+H(Y^n)\\ &= H(\pi_{Y^n}(X^n))+H(\pi_{X^n}(Y^n))+H(\pi_{\pi_{X^n}(Y^n)}(Y^n)) \end{align*}$$

as proven earlier, $\pi_{Y^n}(X^n)$ is independent of $Y^n$, such that:

$$\begin{align*}H(X^{n}Y^{n}) & =H(\pi_{Y^n}(X^n))+H(\pi_{X^n}(Y^n))+H(\pi_{\pi_{X^n}(Y^n)\pi_{Y^n}(X^n)}(Y^n\pi_{Y^n}(X^n)))\\ &= H(\pi_{Y^n}(X^n))+H(\pi_{X^n}(Y^n))+H(\pi_{\pi_{X^n}(Y^n)\pi_{Y^n}(X^n)}(X^nY^n)) \end{align*}$$

Noting $M_{X^nY^n}=\pi_{\pi_{X^{n}}(Y^{n})\pi_{Y^{n}}(X^{n})}\left(X^{n}Y^{n}\right)$, we notice $M_{X^nY^n}$ and $\pi_{X^{n}}(Y^{n})$ represent $Y^n$ since adjoining $\pi_{Y^{n}}(X^{n})$ recovers $X^nY^n$.

Similarly $M_{X^nY^n}$ and $\pi_{Y^{n}}(X^{n})$ represent $X^n$, so there exist two encodings:

• $B_{Y^n}=B_{M_{X^nY^n}}B_{\pi_{X^{n}}(Y^{n})}$
• $B_{X^n}=B_{M_{X^nY^n}}B_{\pi_{Y^{n}}(X^{n})}$

And since,
$$\begin{align*} H(M_{X^{n}Y^{n}}) & =H(X^{n}Y^{n})-H(\pi_{Y^{n}}(X^{n}))-H(\pi_{X^{n}}(Y^{n}))\\ &= H(X^n)-H(\pi_{X^{n}}(Y^{n})) +H(X^{n}Y^{n}) - H(X^{n}Y^{n}) \\ &=H(X^n) + H(Y^n) - H(X^nY^n)\\ & =nC \end{align*}$$

using the asymptotic codelength property and given $\epsilon > 0$:
$$\lim_{n\to\infty}P\left(\left\Vert B_{M_{X^{n}Y^{n}}}\right\Vert \lt n(C-\epsilon)\right)=0$$

Hence, by encoding $Y^n$ and considering the $n(C−\epsilon)$ first bits we are almost certain to recover a prefix of $B_{X^n}$ concluding the reasoning.

Proof of the channel coding theorem (converse)

By contradiction, suppose there exists $f_n$ such that,
$$I(f_n(Y^n),X^n)-nC=|\Omega(n)|$$

since $\pi_{X^n}(Y^n)$ is independent of $X^n$, we would have,
$$I(\pi_{\pi_{X^n}(Y^n)}(f_n(Y^n)),X^n)-nC=|\Omega(n)|$$

but then:
$$\begin{align*}H(Y^{n}) & \geq H(\pi_{\pi_{X^{n}}(Y^{n})}(f_{n}(Y^{n}))\pi_{X^{n}}(Y^{n}))\\H(Y^{n}) & \geq H(\pi_{\pi_{X^{n}}(Y^{n})}(f_{n}(Y^{n})))+H(\pi_{X^{n}}(Y^{n}))\\nC & \geq H(\pi_{\pi_{X^{n}}(Y^{n})}(f_{n}(Y^{n})))\end{align*}$$

Contradiction.