Proof of source coding theorem using asymptotic equipartition property(AEP)

Question

In this wikipedia article, there is a proof given for one of the directions of the Shannon's source coding theorem using the asymptotic equipartition property (AEP). I am unable to follow the proof. Here are the relevant definitions. To get the idea of the proof I wish to see the implication only for a special case (of the direction of interest) of the source coding theorem, which is what I state below.

For a finite set $\Sigma$, we write $\Sigma^*$ to mean the set of all the finite strings than can be formed using the elements of $\Sigma$.

A binary code is a function $c:S\to \{0, 1\}^*$. The extension of $c$ is the function $c^*:S^*\to \{0, 1\}^*$ which is defined as $c(s_1\cdots s_n)=c(s_1)\cdots c(s_n)$, the concatenation of the strings $c(s_i)$'s. A binary code is said to be uniquely decodable if its extension is injective. See this for more context.

Define the length map $\ell:\{0, 1\}^*\to \mathbb N$ which maps a binary string to its length.

Source Coding Theorem. Let $S$ be a finite set and $\mu$ be a probability measure on $S$ and $c:S\to \{0, 1\}^*$ be a uniquely decodable code. Then $\mathbb E[\ell(c)] = \int_S \ell\circ c\ d\mu\geq H_\mu = -\sum_{s\in S}\mu(s)\log_2\mu(s)$.

For each $n\geq 1$ and $\epsilon>0$, equip $S^n$ with the product measure $\mu^n$ and define the set $$A_n^{\epsilon} = \{(s_1, \ldots, s_n)\in S^n:\ \left|-\frac{1}{n}\mu^n(s_1, \ldots, s_n) - H_\mu\right|< \epsilon\}$$

Assume that the following is true (a consequence of AEP)

Consequence of AEP. For each $\epsilon>0$, there is $n$ large enough so that $\mu^n(A_n^\epsilon)>1-\epsilon$.

Now the wikipedia article hints (last line of the section Proof:Source Coding Theorem) that the source coding theorem follows from the fact that "any set of size smaller than $A_n^\epsilon$ (in the sense of exponent) would cover a set of probability bounded away from 1."

I do not even follow what this means and am unable to see how the coding enters the picture here. Can somebody please elaborate on the hint or provide a reference where more details can be found?

Answer 1

Here's what's going on in the proof Wikipedia gave of "achievability". A very small set contains nearly all of the strings that will be generated, probability-wise. I.e., the typical set has an exponentially small proportion of tuples $(x_1,\dots,x_n)$ but has $1-o(1)$ of the probability. Since the typical set is so small, you don't need too many bits to describe the typical set; if a set has $k$ elements, you only need $\log_2(k)$ bits.

And the converse is true. If you want to describe a set of $k$ tuples, you need at least $\log_2(k)$ bits. So if you can compress into fewer than $H_\mu$ bits with probability close to $1$, there is a set of tuples of size less than $2^{H_\mu}$ with probability close to $1$, but there just isn't.