Recently, while studying AI, I naturally began to think a lot from the perspective of Information Theory. In that process, I took another deep look at the theory itself, and since I had not posted much on my blog for a while, I thought this would be a good opportunity to organize and share what I have studied, using the textbook "Elements of Information Theory" as the main reference. I plan to make it as easy to understand as possible, with explanations centered on intuitive examples and accompanied by formulas and proofs only where absolutely necessary.
One thing to note is that although introductions to Information Theory often start with Chapter 2: Entropy, Relative Entropy, and Mutual Information, there are already so many well-organized resources on that topic. Therefore, I will replace that chapter with an attached file containing the notes I studied and organized. (The file is right below.) So, the first post related to Information Theory will start with Chapter 3: Asymptotic Equipartition Property (AEP), which is deeply related to information compression!!
Elements of Information Theory - Chapter 2 Notes
The term Asymptotic Equipartition Property (AEP) might look difficult, but in simple terms, you can understand it as applying the Law of Large Numbers to entropy. In this post, we will work through what that means mathematically. Let me start with the formal definition.
Let’s assume we perform i.i.d. sampling $N$ times from an arbitrary random variable $X_i \sim p(x)$. Then, we can define AEP as follows:
Let’s examine what this means. Usually, the formula for entropy is defined as $- \sum_i p(X_i) \log p(X_i)$. However, since the current situation assumes i.i.d. variables, there is no need to separately consider the $p(X)$ attached in front of the $\log$. Since each random variable is sampled from the same distribution (and the trials are independent), we simply need to divide by $N$. Therefore, for the expectation as well, we use $\mathbb{E}$ rather than the notation $\mathbb{E}_p$, which explicitly indicates the distribution $p(x)$. In other words, the main meaning of AEP is that, for an i.i.d. sequence, the average information converges to the entropy.
Remark 3.1: In Machine Learning, taking the expectation is usually treated the same as simply finding the average. The reason is that we usually assume an i.i.d. situation when sampling data.
Actually, there is one more point we need to examine mathematically. In the formula above, $\frac{1}{N}\sum_i^N \log p(X_i)$ is the sample mean, while $\mathbb{E}\left[ \log p(x) \right]$ is the true mean (or expectation) under the distribution $p(x)$. In other words, the entropy value calculated from a finite sample is not mathematically identical to the true entropy $H(X)$. However, this relationship holds because it has already been proven that the sample mean converges to the expectation of the true distribution. So, let’s take a look at how this can be proven. (The term Law of Large Numbers appeared earlier in the explanation of AEP because of this proof.)
(I will write the proof section in English for convenience.)
Let $X_1, X_2, \ldots, X_N$ be a random sample of $N$ i.i.d. variables from the distribution $p(x)$. Moreover, the mean of the true distribution (population mean) $p(x)$ is defined as $\mathbb{E}[X] = \mu$, and its finite variance is denoted by $\text{Var}[X] = \sigma^2$. Let us first break down the proof for the expectation of the sample mean as follows:
Let the sample mean, denoted by $\bar{X}_ N$, be defined as:
\[\begin{equation*} \bar{X}_ {N} = \frac{1}{N} \sum_ {i=1}^N X_{i} \end{equation*}\]Then, the expectation of the sample mean is given by:
\[\begin{align*} \mathbb{E}\left[\bar{X}_ N \right] = \mathbb{E}\left[\frac{1}{N} \sum_ {i=1}^N X_i \right] = \frac{1}{N}\sum_ {i=1}^N \mathbb{E}\left[ X_i \right] \end{align*}\]Here, since the expectation of each random variable $X_i$ is $\mu$, the expectation of the sample mean becomes:
\[\begin{equation*} \mathbb{E}\left[\bar{X}_ N \right] = \frac{1}{N}\sum_ {i=1}^N \mathbb{E}\left[ X_i \right] = \frac{1}{N} \times N \times \mu = \mu \end{equation*}\]This shows that the expectation of the sample mean equals the true population mean. In other words, the sample mean is an unbiased estimator of the population mean.
Next, the convergence of the sample mean to the true mean can be proved in two ways—through the Weak Law of Large Numbers (WLLN) and the Strong Law of Large Numbers (SLLN). Here, we will focus only on the WLLN, which is sufficient for our discussion of the Asymptotic Equipartition Property (AEP).
First, the WLLN states that the sample mean converges in probability to the population mean. This means that, for any small positive number $\epsilon$, the probability that the sample mean $\bar{X}_ N$ deviates from the true mean $\mu$ becomes arbitrarily small. This can be formally expressed as follows:
\[\begin{equation*} \lim_{n \rightarrow \infty} P(\left| \bar{X}_ N - \mu \right| \geq \epsilon ) = 0 \end{equation*}\]This can be proven using Chebyshev’s Inequality, assuming finite variance $\sigma^2$. Let us first recall Chebyshev’s Inequality, which states that for any random variable $Y$ with mean $\mathbb{E}\left[Y\right]$ and variance ${Var}\left[ Y \right]$:
\[\begin{equation*} P(\left| Y - \mathbb{E}\left[Y\right] \right| \geq \epsilon) \leq \frac{Var\left[ Y \right]}{\epsilon^2} \end{equation*}\]Now, let $Y = \bar{X}_ N$, and we can derive the variance of the sample mean $\bar{X}_ N$ using properties of variance:
\[\begin{align*} Var \left[ \bar{X}_ N \right] &= Var\left[ \frac{1}{N}\sum_ {i=1}^N X_i \right] \\ &= \frac{1}{N^2} Var \left[ \sum_ {i=1}^N X_i \right] \\ &= \frac{1}{N^2} \sum_ {i=1}^N Var\left[X_i \right] \\ &= \frac{1}{N^2} \sum_ {i=1}^N \sigma^2 \;\; (Var[X_i] = \sigma^2 \; \text{for all i}) \\ &= \frac{\sigma^2}{N} \end{align*}\]Since we already know $\mathbb{E}\left[\bar{X}_ N\right] = \mu$ and ${Var}\left[\bar{X}_ N \right] = \frac{\sigma^2}{N}$, we can apply Chebyshev’s Inequality to the sample mean $\bar{X}_ N$:
\[\begin{equation*} P(\left| \bar{X}_ N - \mu \right| \geq \epsilon) \leq \frac{\sigma^2}{N \epsilon^2} \end{equation*}\]As the number of samples $N \to \infty$, the right-hand side approaches 0:
\[\begin{equation*} \lim_{N \rightarrow \infty} P( \left| \bar{X}_ N - \mu \right| \geq \epsilon) = 0 \end{equation*}\]This tells us that the probability of the sample mean deviating from the true mean by more than $\epsilon$ becomes arbitrarily small as the sample size grows. Since probabilities are non-negative, this is equivalent to:
\[\begin{equation*} \lim_{N \rightarrow \infty} P(\left| \bar{X}_ N - \mu \right| < \epsilon) = 1 \end{equation*}\]This completes the proof of convergence in probability of the sample mean to the population mean, as stated by the WLLN. $\Box$
We worked through the concept called AEP earlier, but the reason this concept is important is that it helps us explain the Typical Set. The Typical Set represents the characteristics that a long sequence is expected to have. This may sound a bit confusing, so let me explain it with an example of a coin toss.
Let’s assume we toss a coin a total of 100 times. Since each toss is independent, there are $2^{100}$ possible outcomes consisting of Heads (H) and Tails (T). We can describe the Typical result and Non-typical result as follows:
In other words, in the case of a coin toss, the Typical Set refers to the set of results where the ratio of Heads to Tails is close to 50:50.
To put it more informally, Typical Set can be expressed as a set of probabilistic results that are acceptable within the bounds of common sense.
Now, let’s express the definition of the Typical Set formally. Mathematically, it can be written as follows:
Let $(x_1, \ldots, x_n) \in \mathcal{X}^n$ denote a sequence of length $n$, and let $\epsilon$ be a very small positive number. Then, the typical set ${A}^{(n)}_\epsilon$ with respect to $p(x)$ is the set of sequences with the following property:
\[\begin{align*} 2^{-n(H(X)+\epsilon)} \leq p(x_1, x_2, &\ldots, x_n)\leq 2^{-n(H(X)-\epsilon)} \end{align*}\]By applying logs, if $(x_1, \ldots, x_n) \in A_\epsilon^{(n)}$, then
\[\begin{align*} {-n(H(X)+\epsilon)} &\leq \log p(X_1, X_2, \ldots, X_n)\leq {-n(H(X)-\epsilon)} \\ {H(X)-\epsilon} &\leq -\frac{1}{n}\log p(X_1, X_2, \ldots, X_n)\leq {H(X)+\epsilon} \end{align*}\]This means that the average log-probability, $\frac{1}{n}\sum_i \log p(X_i)$, is bounded by the entropy $H(X)$ and $\epsilon$. More precisely, this is called the $\epsilon$-Typical Set.
However, if you look closely, the term $-\frac{1}{n}\sum_i \log p(X_i)$ in the middle shows a close relationship with the AEP explained above. Based on AEP, we can establish the properties of the typical set $A_\epsilon^{(n)}$. Now, let’s examine the properties of $A_\epsilon^{(n)}$ and the proofs for them.
From the Asymptotic Equipartition Property (AEP), we know that
\[\begin{equation*} -\frac{1}{n}\sum_ {i=1}^n \log p(X_i) \rightarrow H(X) \end{equation*}\]in probability. This implies that when $n$ is sufficiently large,
\[\begin{align*} p \underbrace{\left(\left|-\frac{1}{n}\log p(X_1, \ldots, X_n) - H(X) \right| \leq \epsilon \right)}_ {\in A_ \epsilon^{(n)}} \geq 1 - \delta, \end{align*}\]where $\delta$ is a small positive number, consistent with the convergence in probability. In the case where $\delta = \epsilon$, this satisfies the first property. $\Box$
We can derive a lower bound on the probability mass of the typical set based on its definition:
\[\begin{align*} 1 &= \sum_ {\mathbf{x} \in \mathcal{X}^n} p(\mathbf{x}) \\ &\geq \sum_ {\mathbf{x} \in A^{(n)}_ \epsilon} p(\mathbf{x}) \\ &\geq \sum_ {\mathbf{x} \in A^{(n)}_ \epsilon} 2^{-n(H(X) +\epsilon)} \scriptsize{\text{(by the lower bound of the Typical Set definition)}}\\ &= 2^{-n(H(X) +\epsilon)} |A^{(n)}_ \epsilon|. \end{align*}\]Multiplying both sides by $2^{n(H(X) +\epsilon)}$ yields $\rvert A^{(n)}_ \epsilon\rvert \leq 2^{n(H(X) +\epsilon)},$ which satisfies the second property. $\Box$
From the first property, we can derive an upper bound as follows:
\[\begin{align*} 1 - \epsilon &\leq p(A_\epsilon^{n}) \\ &\leq \sum_ {\mathbf{x} \in A^{(n)}_ \epsilon} 2^{-n(H(X) -\epsilon)} \scriptsize{\text{(by the upper bound of the Typical Set definition)}}\\ &= 2^{-n(H(X) -\epsilon)} |A^{(n)}_ \epsilon|. \end{align*}\]Multiplying both sides by $2^{n(H(X) - \epsilon)}$ gives $\rvert A^{(n)}_ \epsilon\rvert \geq 2^{n(H(X) - \epsilon)},$ which satisfies the third property. $\Box$
We have examined the concept of AEP and the $\epsilon$-Typical Set. So, what can we do with these properties? There are several possible applications, but the most useful one is data compression. In other words, compressing data to near-lossless becomes possible through AEP. Let’s see how this works through an example.
Let’s use a coin toss as an example again. To make the example more extreme, let’s assume the probabilities are not equal: Heads (H) 90% (P(H)=0.9) and Tails (T) 10% (P(T)=0.1). In this case, the possible outcomes are as follows:
Next, thinking simply, when tossing the coin 3 times, the expected number of Heads (H) is $3 \times 0.9 = 2.7$. If we make the range slightly wider, we can say that Heads will appear about 2 or 3 times (lower bound = 2, upper bound = 3). In other words, getting Heads (H) 2 or 3 times can be considered typical. Now, calculating $A^{(3)}$ based on Heads (H) gives:
$A^{(3)} = P(HHH) + P(H\times2,T)\times3 = 0.729 +0.081 \times 3 = 0.972$
That is, intuitively, the probability of the Typical Set occurring is about 97.2%. It is very close to 100%.
However, this example is too small, with $n=3$, so it is difficult to apply the properties of AEP and the Typical Set defined above. This is because those properties assume that $n$ is sufficiently large. Therefore, based on the intuition above, let’s examine what happens mathematically when we increase it to $n=100$.
From now on, since we need to use the value of entropy directly in the formula, let’s calculate the entropy $H$ for the probability of Heads appearing. Calculating the binary entropy $H(p)$ (for a binomial trial) gives:
\[\begin{align*} H(p) &= -p\log p - (1-p)\log (1-p) \;\; \scriptsize{\text{(Entropy for Binomial Trial)}}\\ H(0.9) &= 0.9 \log 0.9 - (1-0.9)\log 0.9 \\ &= 0.9 \log 0.9 - 0.1\log0.1 \\ &\approx 0.1368 + 0.3322\\ &\approx 0.469 \end{align*}\]In other words, the entropy based on Heads (H) per toss is about ${H(0.9) = 0.469}$. Now, substituting this into the Typical Set $A_{\epsilon=0}^{(n)}$ gives:
\[\begin{equation*} |A^{(n)}_{\epsilon=0}| = 2^{nH} = 2^{100\times0.469} = 2^{46.9} \approx 1.2\times10^{14} \end{equation*}\]Let’s examine the meaning of this result from the perspective of Information Theory and bits.
First, as in the example above, let’s calculate the probability of the Typical Set occurring. When $n=3$, it was difficult to set a bound, so we simply chose the range 2 to 3 without setting $\epsilon$ separately. However, since $n=100$ now, we can set the lower and upper bounds of the Typical Set using $\epsilon$. For convenience, let’s say the expected count is $100 \times 0.9 = 90 =np$, and calculate the Typical Set with a bound of $\pm 5$. (Range of expected Heads: $N_H \in [85, 95]$)
\[\begin{align*} p(A^{(100)}_ \epsilon) &= \sum_ {k=85}^{95} p(N_H=k)\\ &=\sum_ {k=85}^{95}\binom{100}{k}p^k (1-p)^{100-k} \\ &\approx 0.936 \end{align*}\]This means that the sum of the probabilities of the cases belonging to the Typical Set accounts for about 93.6% of the total probability mass among the $2^{100}$ possible cases. Although it is not 100%, most of the probability mass is included in the Typical Set.
Now, imagine communicating information about what happened above to someone. The total number of ways to convey information about the coin toss is $2^{100}$ (the size of the total set $\mathcal{X}$; $\rvert \mathcal{X}\rvert $). If we think about transmitting this in bits, we would need $\log2^{100} = 100$ bits (excluding the prefix). However, the size of the Typical Set calculated above is about $\log2^{46.9} = 46.9$ bits $ \approx 47$ bits. (We express this through indexing.) If we transmit only the Typical Set, we can save about $53$ bits. From a communication perspective, this is a very large amount of compression. ($53\%$ compression is possible.)
To summarize, if we are communicating information about an event consisting of 100 coin tosses, the Typical Set allows us to communicate events corresponding to about 93.6% of the total probability mass with about 47 bits. In other words, this uses 53% fewer bits than before.
One-line summary: Let's compress the frequently occurring sets, and leave the rarely occurring sets as they are!
Now, let’s look at this formally from the perspective of sequence length. First, the Typical Set $A^{(n)}_ \epsilon$ defined earlier satisfies the following property:
\[\begin{equation*} |A^{(n)}_ \epsilon| \leq 2^{n(H + \epsilon)} \end{equation*}\]In other words, most sequences are included in this Typical Set, and their number is at most $2^{n(H+\epsilon)}$. As explained in the example, this means that sequences within this Typical Set can be represented using approximately $n(H + \epsilon) + 1$ bits. (Here, +1 accounts for the case where $n(H + \epsilon)$ is not an integer.) Additionally, since we need 1 bit to indicate whether a sequence belongs to the Typical Set, the total length can be represented using $n(H + \epsilon) +2$ bits. Now, there is another point to examine: as explained above, we compress the Typical Set through indexing and leave the non-typical set as it is. We can express the total length of each as follows:
Now we can calculate the expected value of the sequence length. First, let $x^n$ denote the sequence $(x_1, \ldots, x_n)$, and let $l(x^n)$ denote its length. Then, the expected value of the required sequence length can be expressed as follows:
\[\begin{align*} \mathbb{E}\left[ l(X^n) \right] &= \sum_ {x^n} p(x^n)l(x^n)\\ &= \sum_ {x^n \in A^{(n)}_ \epsilon } p(x^n)l(x^n) + \sum_ {x^n \in A^{(n)^c}_ \epsilon} p(x^n)l(x^n)\\ &\leq \sum_ {x^n \in A^{(n)}_ \epsilon } p(x^n)\left(n(H + \epsilon) + 2\right) + \sum_ {x^n \in A^{(n)^c}_ \epsilon} p(x^n)\left(n\log |\mathcal{X}| + 2 \right)\\ &= p(A^{(n)}_ \epsilon )\left(n(H + \epsilon) + 2\right) + p(A^{(n)^c}_ \epsilon )\left(n\log |\mathcal{X}| + 2 \right)\\ \end{align*}\]Another point to consider is that we want to know not only how many bits are used for the entire sequence $X^n$, but also how many bits are required for each $x_i$. That is, we need the average number of bits (the bit rate) $\frac{1}{n} \mathbb{E}[l(X^n)]$, not the total number of bits $\mathbb{E}[l(X^n)]$. We can summarize this as follows:
Let $X^n \sim p(x)$ and let $\epsilon > 0$. Then, for sufficiently large $n$, the following holds:
\[\begin{equation*} \mathbb{E}\left[\frac{1}{n}l(X^n) \right] \leq H(X) + \epsilon \end{equation*}\]This Theorem follows from the expectation calculated just above. First, when $n\rightarrow \infty$, $p(A^{(n)}_ \epsilon)$ and $p(A^{(n)^c}_ \epsilon)$ converge to $p(A^{(n)}_ \epsilon) \rightarrow 1$ and $p(A^{(n)^c}_ \epsilon) \rightarrow 0$, as seen in Property 1. Then, $\mathbb{E}\left[ l(X^n) \right] \leq n(H + \epsilon) + 2$, and dividing both sides by $n$ leads to Theorem 2.
In conclusion, when $n\rightarrow\infty$, the entire sequence $X^n$ can be compressed to approximately (or, more precisely, weakly) $nH$ bits.
To briefly summarize what we covered:
Theorem 1):Definition 1, Properties 1):Definition 1:Properties 1
Theorem 2)In this chapter, we examined how information can be efficiently compressed and transmitted, using intuitive explanations while also looking at how this is mathematically possible. Whenever I have time in the future, I plan to organize more key concepts from Elements of Information Theory, especially those that are important from an AI research perspective.
Then, I’ll see you again in the next post!