Entropy

Entropy

Definition

The entropy of a random variable $X$ is defined as

Here we adopt the convention that $0 \log 0 = 0$, as $\lim_{x \rightarrow 0^+} x \log x = \lim_{x \rightarrow \infty} \frac{1 }{ x } \log \frac{1 }{ x } = 0$.

Properties

The entropy is oblivious to the specific values $X$ takes and is only sensitive to the probabilities with which $X$ takes these values. Further, the entropy of a random variable may not reflect the whether a random variable is concentrated at its mean or not.

Example.

1. $X_1 = \begin{cases} e^{1000}, \text{with probability 0.5} \\ 0, \text{with probability 0.5} \end{cases}$
2. $X_2 = \begin{cases} 1, \text{with probability 0.5} \\ -1, \text{with probability 0.5} \end{cases}$

Both $\mathbf{H}[X_1] = \mathbf{H}[X_2] = 0.5 \log_2 2 + 0.5 \log_2 2 = 1$.

The binary entropy function $\mathbf{H}(p)$ of a Bernoulli random variable $X$ that takes value $1$ with probability $p$ is

By concavity of $\log_2(\cdot )$, we know that

The equality holds when $p = 0.5$.

Some interesting values:

• $p = 0.5$, $\mathbf{H}(p) = 1$
• $p = 0.2/0.8$, $\mathbf{H}(p) \approx 0.7$
• $p = 0.1/0.9$, $\mathbf{H}(p) \approx 0.5$

Lemma. Given a discrete range $\mathcal{U}$, the entropy of a random variable $X$ defined on $\mathcal{U}$ is maximized when $X$ has uniform distribution, i.e.,

$$\mathbf{H} (X) \le \log |\mathcal{U}|$$

Proof.

The inequality holds with equality only when $p(x) = 1/ |\mathcal{U}|$.

$\blacksquare$

Lemma. Let $p(x)$ and $q(x)$ be two distributions and $\lambda \in [0, 1]$, then

$$\mathbf{H} (\lambda p(x) + (1 - \lambda) q(x) ) \ge \lambda \mathbf{H}(p(x) ) + (1 - \lambda) \mathbf{H} (q(x) )$$

Proof.

$\blacksquare$

Lemma. For two independent random variables $X$ and $Y$, we have

$$\mathbb{E} \left[ \log_2 \frac{1}{\Pr[X + Y] } \right] = \mathbb{E} \left[ \log_2 \frac{1}{\Pr[X] } \right] + \mathbb{E} \left[ \log_2 \frac{1}{\Pr[Y] } \right],$$

i.e.,

$$\mathbf{H}[X + Y] = \mathbf{H}[X] + \mathbf{H}[Y].$$

Proof. We prove it for the case of discrete random variables.

$\blacksquare$

Joint Entropy and Conditional Entropy

Definition. Given random variable $X$ and $Y$, the joint entropy $\mathbf{H}(X, Y)$ with a distribution $p(x, y)$ is defined as

$$\mathbf{H}(X,Y) = \mathbb{E}\left[ \log \frac{1}{p(x, y)} \right].$$

When $X$ and $Y$ are discrete random variables, it is equivalent to

$$\mathbf{H}(X,Y) = \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{p(x, y) }.$$

Definition. The conditional entropy $\mathbf{H}(Y \mid X)$ with a distribution $p(x, y)$ is defined as

$$\begin{aligned} \mathbf{H}(Y \mid X) &= \sum_{x \in \mathcal{X} } p(x) \cdot \mathbf{H} (Y \mid X = x) \\ &= \sum_{x \in \mathcal{X} } p(x) \cdot \sum_{y \in \mathcal{Y} } p(y \mid x) \log \frac{1}{p(y \mid x) } \\ &= \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{p(y \mid x) } \\ &= \mathbb{E} \left[ \log \frac{1}{p(y \mid x) } \right] \end{aligned}$$

• Remark. Conditioned on $X = x$, $Y$ is a random variable and therefore we can define its Entropy as $\mathbf{H}(Y \mid X = x)$. The conditional entropy $\mathbf{H}(Y \mid X)$ is the average of the $\mathbf{H}(Y \mid X = x)$ over the distribution of $X$, i.e., the average uncertainty in $Y$ after we had observed $X$. Both $\mathbf{H}(Y \mid X)$ and $\mathbf{H}(Y \mid X = x)$ represent a value. This is different from the conditional expectation: $\mathbb{E}[Y \mid X]$ is a random variable and $\mathbb{E}[Y \mid X = x]$ is a value.

Chain Rule. For random variable $X$ and $Y$, it holds that

$$\begin{aligned} \mathbf{H}(X, Y) &= \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{p(x, y) } \\ &= \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{p(y \mid x) p(x) } \\ &= \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{p(y \mid x) } + \sum_{x \in \mathcal{X} } \sum_{y \in \mathcal{Y} } p(x, y) \log \frac{1}{ p(x) } \\ &= \mathbf{H}(Y \mid X) + \mathbf{H}(X) \end{aligned}$$

Corollaries

Or

Binomial Distribution

We study the relationship of binomial distribution $B(n, p)$ and entropy. As a rule of thumb, for reasonably large $n$ (say, $n \ge 100$) and moderate size of $p$ (e.g., $0.1 \le p \le 0.9$), the probability is concentrated on the interval $[np - \sqrt n, np + \sqrt n]$.

$N = 100, p = 0.5$.

$N = 100, p = 0.3$.

$N = 100, p = 0.1$.

$N = 1000, p = 0.1$. Note that

Lemma. For $n\in \mathbf{Z}^+$, $k \in [n]$, it holds that

Proof. Define $q = \frac{k}{n}$. Then

The summation consists of $(n + 1)$ terms. We claim that

is the largest one. For $i \in [n]$,

The ratio is at least $1$ when $\frac{n - i}{i + 1} \ge \frac{1 - q}{ q }$. We see that when $i = nq - 1 = k - 1$, it holds that

and when $i = k$,

Therefore,

$\blacksquare$

Extracting Random Bits

Consider a uniform random variable $X$ at $[0, m - 1]$. By definition we know that

Given $X$ as an input, the following algorithm outputs a binary string $s$, such that each bit of $s$ can be interpreted as the outcome of independently Bernoulli random variables with probability $0.5$.

On the high level, we divide $m$ into intervals of powers of 2. When $X$ falls into an interval, we return a binary number that is within the range of that interval. Specifically, we rewrite

where $\lfloor \mathbf{H}[X] \rfloor = \lfloor \log_2 m \rfloor = d_k > d_{k - 1} > ... > d_1 \ge 0$ are the indexes of non-zero bits in the binary representation of $m$. The extraction is as follows:

Algorithm 1.

1. for $i \leftarrow k$ down-to $1$ do:
2. $\quad$ if $X < 2^{d_i}$ then:
3. $\quad$ $\quad$ return a $d_i$-bit binary representation of $X$;
4. $\quad$ else:
5. $\quad$ $\quad$ $X \leftarrow X - 2^{d_i}$;

Example ($m = 13$). It is interesting to note that when $X = 12$, our proposed extraction method return no random bit, as $0 < 2^0$. In this case our proposed method has wasted some randomness.

Question to ponder: Come up with some method that uses $n$ i.i.d. $X$'s to extract binary string with expected length close to $n \mathbf{H}[X]$.

Let $s$ be the binary string returned by Algorithm 1.

Theorem 1.

Proof. It is easy to see that

which depends on $m$. To show the upper bound,

The inequality follows from $\log_2 \frac{2^{d_i} }{m } \le 0$ for $1 \le i \le k$.

To show the lower bound, define the function

We prove by induction on $m$ that $f(m) \ge \lfloor \log_2 m \rfloor - 1 = d_k - 1$. The cases holds trivially when $m = 1$. Now suppose it holds for all integer less than $m$. We prove that it holds for $m$.

Case 1. $m = 2^{d_k}$. Then $f(m) = d_k = \log_2 m$.

Case 2. $m > 2^{d_k}$. Now

But $\sum_{i = 1}^{k - 1} 2^{d_i} = m - 2^{d_k}$. It follows by induction

Finally,

The last inequality holds since $d_{k - 1} \le d_k - 1$ and the function $f(x) = \frac{x + 1}{2^x}$ decreases when $x \ge 1$.

$\blacksquare$

Binary Strings

To illustrate the idea of entropy, we study another example of random bit extraction.

Problem. Let $t$ be an $n$-bit binary string each bit of which is interpreted as the outcome of independent bias coin flip that comes up head probability $p \le 0.5$. Given $t$ as input, we want to output a binary string $s$ (not necessary of length $n$) of independent unbiased random bits.

Theorem. There is an extraction algorithm, such that,

1. $\forall \delta \in (0, 1)$, $\exists N > 0$, $s.t.$, $\forall n \ge N$, $\mathbf{E}[|s|] \ge (1 - \delta) n\mathbf{H}(p)$.
2. $\forall n > 0$, $\mathbf{E}[|s|] \le n\mathbf{H}(p)$.

The theorem states that the expected length of $s$ approximates $n\mathbf{H}(p)$. Equivalently,

Proof. Define the random variable $Z$ to be the number of ones in $t$. For any integer $k \ge 0$, there are $\binom{n}{k}$ strings with $k$ ones. We can map these strings to $\{0, 1, ..., \binom{n}{k} - 1 \}$. Conditioned on $Z = k$, the mapping of $t$ is uniform on $\{0, 1, ..., \binom{n}{k} - 1 \}$. We can use Algorithm 1 to return a binary string $s$. Now its expected length is

Further, by Hoeffding's inequality, it holds that for $0 < \epsilon < p$,

By setting the failure probability $\exp(-2 n \epsilon^2) = \delta / 2$, we get $\epsilon = \sqrt{\frac{\ln \frac{2}{\delta} }{2n} }$.

Let $LB = \lceil np - n\epsilon \rceil$ and $UB = \lfloor np + n\epsilon \rfloor$. Observing that $Z$ is an integer, we have

As $p \le 0.5$, it holds that

Therefore,

Since $\binom{n}{k}$ increase for $k < n / 2$ and decrease $k > n / 2$, it holds that

For $LB \le k \le UB$, we have

Define $q = \frac{ LB }{n}$,

By Theorem 1, we have

$\exists N > 0$, s.t., $\forall n > N$, $\left( \frac{\mathbf{H} \left(p - \sqrt{\frac{\ln \frac{2}{\delta} }{2n} } \right) }{\mathbf{H}(p) } - \frac{\log_2 (n + 1) }{ n\mathbf{H}(p) }\right) \ge (1 - \delta / 2)$, which finishes the proof of lower bound.

As for the upper bound, observe that

Therefore, $\binom{n}{k} \le p^{-k} ( 1- p)^{-(n - k) }$. Thus, we have

The last term is exactly the entropy of the string. By independence of the bits, we know that it is equal to $n \mathbf{H}(p)$.

Remark: we may also prove it algebraically.

$\blacksquare$

Reference.

[1] S. Har-Peled, “Chapter 26 Entropy, Randomness, and Information,” p. 6.
[2] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge: Cambridge University Press, 2005.