Entropy and Compression

One interpretation of entropy of a random variable is as a measure of how many unbiased, independent random bits in expectation we can extract from the random variable. Another one comes from compression of a sequence.

Assume that the sequence studied (denoted as $s$) is a binary one. It consists of a concatenation of the outcomes of $n$ independent Bernoulli random variables. Without lose of generality, we assume that each bit comes up $1$ with probability $p \le 1 / 2$. This is one of the simplest models of a sequence.

The fact that sequence could be a biased one makes it possible to represent it by a new sequence with shorter length in expectation. For example, suppose that $p = \frac{1}{4}$, then for a pair of consecutive bits, it have

1. probability $\frac{1}{16}$ of being $11$,
2. probability $\frac{3}{16}$ of being $01$,
3. probability $\frac{3}{16}$ of being $10$,
4. probability $\frac{9}{16}$ of being $00$.

If we use $111$ to represent $11$, $110$ to represent $01$, $10$ to represent $10$, and $0$ to represent $00$, then the expected number of representation bits per pair is

In general, compression is not limited to the way described above. We call the rule with which we compress a string a compression function.

Compression Function

Definition. Let $S = \{0, 1\}^n$ be the set of binary sequence of length $n$, and $T = \{ 0, 1\}^+$ the set of binary sequence of any positive length. A compression function $h: S \rightarrow T$ is an injective (one-to-one) function from $S$ to $T$.

In other words, each $s \in S$ is assigned a unique non-empty sequence (of arbitrary length) by $h$.

Observe that the size of $S$ is $2^n$. On the other hand, the number of sequences with length less than $n$ is $\sum_{i = 1}^{n - 1} 2^{i} = 2^n - 1 < 2^n$. For any $h$, it is impossible for $h$ to map every $s \in S$ to a sequence with length less than $n$. Under adversarial input, $h$ can not compress at all.

The hope is that when there is a distribution $\mathfrak{D}$ on $S$, the expected length of the compressed sequences would be small:

To illustrate the meaning of entropy, we study a simple case where $\mathfrak{D}$ is the joint distribution of $n$ i.i.d. Bernoulli random variables that come up $1$ with probability $p \le { 1 / 2 }$ (by symmetry, the claim holds for the case of $p > { 1 / 2 }$).

The following theorem formalizes how good a compression function we can find.

Entropy as Lower and Upper Bounds

Theorem.

1. $\forall \delta > 0$, $\exists$ a compression $h$ and integer $N > 0$, s.t., $\forall n \ge N$, it holds that

$$\mathbf{E}[ |h(s)| ] \le (1 + \delta) n \mathbf{H}(p)$$

2. $\forall \delta > 0$, $\exists$ integer $N > 0$, s.t., $\forall n \ge N$, it holds that for any compression $h$,

$$\mathbf{E}[ |h(s)| ] \ge (1 - \delta) n \mathbf{H}(p)$$

Intuitively, the entropy $\mathbf{H}(p)$ is the measure of the average number of bits in expectation we need after compression to represent a Bernoulli random variable that comes up $1$ with probability $p$.

The high level idea of the proof is that, with high probability, the number of ones in a $s \in S$ is roughly $np$. There are roughly $2^{n\mathbf{H}(p)}$ such sequences. Therefore, we can use $n \mathbf{H}(p)$ bits to represent each sequence.

Proof. The claim is trivially true if $p = { 1 / 2 }$. Otherwise, $p < { 1 / 2 }$. We can pick some $\epsilon > 0$, such that $p + \epsilon < { 1 / 2 }$. Further, if $n$ is large enough, $np + n\epsilon \le n / 2 - 1$. Hence, we may assume that $\lceil np + n\epsilon \rceil \le n / 2$ .

Denote $Z$ be the number of ones in the string $s$. By Hoeffding Inequality, it holds that

By the fact that $Z$ takes only integer values, we have

We use the first bit output of $h$ as a flag. For a string $s$ with $Z \ge \lceil np + n\epsilon \rceil$, we set the first bit to $0$ and then output the same sequence, i.e., $h(s) = 0 \circ s$. In such case we do not compress the string at all and use $n + 1$ bits to represent it.

We set the first bit output to $1$ if $Z < \lceil np + n \epsilon \rceil \le n / 2$. The number of such sequences is bounded by

The first inequality holds because $\binom{n}{k}$ increases for $k < n / 2$ and that the summation is over $\lceil np + n \epsilon \rceil \le n / 2$ terms. The last inequality holds since $(\lceil np + n\epsilon \rceil - 1) / n \le ( np + n\epsilon ) / n = p + \epsilon < 1 / 2$ and $\mathbf{H}( \cdot )$ is a increasing function in the range $[0, 1/2]$.

We compress these sequences by representing each of them with a unique sequence of at most

bits. Considering the leading flag bit 1 (to indicate the sequence is a compressed one), we output at most $n \mathbf{H} \left( p + \epsilon \right) + \log n$ bits for sequences with $Z < \lceil np + n \epsilon \rceil$. This can be written as $\left[ \mathbf{H} \left( p + \epsilon \right) + (1 / n) \cdot (\log n - 1) \right] n$ bits and is smaller than

is $\epsilon$ is smaller enough and $n$ is large enough.

We are almost done with the proof. It is left to consider sequences with $Z \ge \lceil np + n \epsilon \rceil$. For those sequence, we don't compress them and and set the leading flag bit to 0. The outputs for those sequences consist of at most $1 + n$ bits. However, by Hoeffding inequality, such sequences do not appear frequently and the expected output length can be made arbitrary small.

Specifically, $\forall \delta > 0$, we can find large enough $N$, such that $\forall n > N$, it holds

Then, in expectation, the bits outputted by $h$ is at most

To prove the lower bound, first we need the following lemma.

Lemma. for $s_1, s_2 \in S$, if $s_1$ has more ones than $s_2$, i.e., $\Pr(s_1) \ge \Pr(s_2)$, then the $h$ that minimizes the expected output length $\mathbf{E}[ |h(s)| ]$ should assign $s_1$ a sequence at most as long as $s_2$, i.e., $|h(s_1)| \le |h(s_2)|$.

Proof. Otherwise, if we swap the output sequences of $h(s_1)$ and $h(s_2)$, we lower value of $\mathbf{E}[ |h(s)| ]$.

$\square$

Further, consider the number of $s \in S$ with $\lfloor np - n \epsilon \rfloor$ ones,

Let $k = \lfloor n \cdot \mathbf{H}( p - \epsilon -1 / n) - \log (n + 1) \rfloor$. For large enough $n$, it holds that

Further, since

there are strictly less than $2^k$ distinct binary sequences with length at most $k - 1$.

Therefore, for the set of $s \in S$ with $\lfloor np - n\epsilon \rfloor$ ones, at least one of them has output length at least $k$.

By the previous lemma, all sequences with more than $\lfloor np - n\epsilon \rfloor$ ones has length at least $k$.

Denote $Z$ be the number of ones in the string $s$. By Hoeffding Inequality, it holds that

By the fact that $Z$ takes only integer values, we have

The expected output length of the sequences with more than $\lfloor np - n\epsilon \rfloor$ ones is at least

This is at least $(1 - \delta) \cdot n \cdot \mathbf{H}(p)$ when $n$ is large enough.

$\blacksquare$

Huffman Code

In this section, we show that the upper bound can be achieved by Huffman code.

$\forall \delta > 0$, $\exists$ a compression $h$ and integer $N > 0$, s.t., $\forall n \ge N$, it holds that

$$\mathbf{E}[ |h(s)| ] \le (1 + \delta) n \mathbf{H}(p)$$

We begin with an important property of Huffman Code. Suppose that we have an alphabet $\mathbb{U}$ such that probability associated with each element in $\mathbb{U}$ is $2^{-l}$ for some integer $l$. Then $\exists h$, such that

For example, if $\mathbb{U} = \{0, 1, 2, 3 \}$ and the distribution $p = \{ 0.5, 0.25, 0.125, 0.125 \}$, then we can have the following encoding

The expected coding length is

which is exactly the entropy of the random variable.

In general, if we have a random variable $X$, we can round down its probability to the nearest integer negative power of $2$. The expected code length is given by

Intuitively, the $\left\lceil \log \frac{1}{p_i} \right\rceil$ has enough slot to accommodate all elements with probabilities $p_i$'s.

In particular, we view $\{0, 1\}^n$ as a large alphabet $\mathbf{\Sigma }$. The alphabet has entropy $n \cdot \mathbf{H}(p)$. We can have a encoding such that the expected output length is at most $n \cdot \mathbf{H}(p) + 1$. For large enough $n$, this is at most $(1 + \delta) n \cdot \mathbf{H}(p)$.

Reference

[1] M. Mitzenmacher and E. Upfal, Probability and computing: an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005.