Introducing Informational Entropy

Problem

The concept of entropy in a thermodynamic context is directly tied to the multiplicity ($\Omega$) of accessible microstates. A remarkably similar idea exists in information theory, where entropy quantifies the actual information content of a bit string, setting a fundamental limit on how efficiently it can be compressed.

Typically, we deal with a system described by a probability distribution over possible outcomes. We begin with the simplest case: a binary string where the probability of encountering a 0 is $p(0) = p$ and a 1 is $p(1) = 1-p$. (Note: Throughout this problem, all logarithms are base 2, i.e., $\log \equiv \log_2$.)

1. Calculate the multiplicity $\Omega$, i.e., the total number of distinct $n$-bit strings containing exactly $np$ 0's and $n(1-p)$ 1's.

2. To uniquely map all $\Omega$ possible configurations into $k$-bit compressed strings, we require $2^k \ge \Omega$. Using Stirling's approximation in the limit of large $n$, show that the minimum required length is $k = n H(p)$, where the Shannon entropy $H(p)$ is defined as

   $$H(p) = -p\log p - (1-p) \log (1-p) \, . \tag{1}$$

3. Examine the properties of the Shannon entropy $H(p)$:

   • For what value(s) of $p$ does $H(p)$ reach its minimum and maximum?

   • What symmetry does $H(p)$ have?

   • How many "logical" bits are contained in $n$ "physical" bits?

   • Is it plausible to interpret $H(p)$ as both (i) the optimal compression ratio and (ii) the average number of logical bits per physical bit?

4. By the time this problem was written, this document contained $58{,}574$ 0's and $48{,}738$ 1's when converted to binary. What is the total Shannon entropy of this document (in bits)? How many bits can it be compressed into?

5. Now generalize Eq. (1) to a system with $d$ discrete outcomes with probability distribution $\{ p_1, p_2, \dots, p_d \}$ satisfying $p_i \ge 0$ and $\sum_{i=1}^d p_i = 1$. By considering the multinomial multiplicity $\Omega = n! / \prod_{i=1}^d (n p_i)!$ of an $n$-character string, show that the generalized Shannon entropy per character is

   $$H(p_1, \dots, p_d) = -\sum_{i=1}^d p_i \log p_i \, . \tag{2}$$

6. Alternatively, we can divide a binary file into 8-bit chunks (bytes), matching standard ASCII character encoding. The table below lists the 10 most frequent characters and their counts in this document:

   ␣	2225	n	516
   e	1099	o	500
   t	965	r	484
   i	690	s	482
   a	622	\	396

   Assuming the entire document only consists of these 10 characters, approximate the entropy $H$. Does $H$ exceed 1? Why is that result consistent?

Solution

1. It is just choosing where the $np$ $0$'s should go among $n$ places.

   $$\Omega(p) = \binom{n}{np} = \frac{n!}{(np)!(n-np)!} \tag{3}$$

2. Using Stirling's approximation,

   $$\begin{align*} k &\ge \log \Omega \\ &= \log n! - \log (np)! - \log (n-np)! \\ &\approx n \log n - n - [np \log (np) - np] - [(n-np) \log(n-np) - (n-np)] \\ &= -n [p \log p + (1-p) \log (1-p)] \\ &= n H(p) \end{align*}$$

3. Some properties of the Shannon entropy are:

   • $H(p)$ has a minimum value of $0$ at $p=0$ and $p=1$; and the maximum value of $1$ at $p=1/2$. This is in agreement with our intuition that we have zero uncertainty about obtaining $0$ (or $1$) with unit probability and that we have maximum uncertainty when the probabilities for getting $0$ and $1$ are equal.

   • $H(p)$ is symmetric with respect to $p=1/2$; we would still have the same amount of uncertainty about the information source if we obtained $0$'s with probability $1-p$.

   • We can interpret the results as $n$ "physical" bits containing $k = nH(p)$ "logical" bits.

   • So it follows that $H(p)$ can be understood in both ways.

4. $0$'s appear with probability $0.5458$ and $1$'s with probability $0.4542$.

   $$H(0.5458) = 0.9939$$

   Effectively, $0.9939$ logical bits are contained in a single physical bit. It cannot be compressed efficiently.

5. We begin with the same idea of taking logarithm to the multiplicity:

   $$\begin{align*} \Omega &= \frac{n!}{\prod_{i=1}^d (np_i)!} \\ \log \Omega &= \log n! - \sum_{i=1}^d \log (np_i)! \\ &\approx n \log n - n - \sum_{i=1}^d [ np_i \log (np_i) - np_i ] \\ &= -n\sum_{i=1}^d p_i \log p_i \end{align*}$$

   In the last line we define the $n$-independent part as the generalized entropy (including the minus sign).

6. If you convert the letter frequencies into probabilities and calculate with the formula obtained in the previous problem, you get $3.079$. This should be interpreted as `containing $3.079$ logical bits per physical byte (8 bits)'. Although the entropy value itself may exceed 1, this is still consistent with our intuition that the optimal compression ratio cannot exceed 1.