3. Asymptotic Equipartition Property

Entropy measures the average surprise of one observation. What does it tell us about a long sequence of observations? Suppose a coin lands heads 90% of the time. The all-heads sequence is the most likely individual outcome, yet a long run usually contains some tails. To understand what we will actually observe, we need to consider whole collections of sequences and their combined probability.

The asymptotic equipartition property (AEP) explains what happens when we draw many independent observations from the same distribution. For a long sequence of $n$ observations, the total surprise $-\log p(X^n)$ is usually close to $nH(X)$. Equivalently, the probability of the sequence we observe is usually around $2^{-nH(X)}$.

These sequences form the typical set, which contains almost all the probability. Roughly speaking, if each sequence contributes probability $2^{-nH(X)}$, we need about $2^{nH(X)}$ of them for their probabilities to add up to one. To encode a typical sequence, we can send its index in this set. Choosing among about $2^{nH(X)}$ indices takes about $\log (2^{nH(X)})=nH(X)$ bits. The bounds below make these approximations precise.

We will derive the AEP, count typical sequences, and use that count to explain compression and the size of high-probability sets.

Assumptions and notation

Let $X_1,X_2,\dots$ be independent and identically distributed (i.i.d.) with PMF $p(x)$ on a finite alphabet $\mathcal{X}$. Write $X^n=(X_1,\dots ,X_n)$ for the random block and $x^n$ for a realization. All logarithms are base 2, so $\log$ means ${\log }_2$ and entropy and surprise are measured in bits. We restrict attention to symbols with positive probability.

---

1. From Average Surprise to the AEP

The probability of a particular sequence factors as

$$p(x^n)=\prod _{i=1}^{n}p(x_i).$$

Taking a negative logarithm turns this product into a sum:

$$-\frac{1}{n}\log p(X^n)=\frac{1}{n}\sum _{i=1}^n[-\log p(X_i)].$$

The expression on the left is random: we first draw a sequence, then evaluate the probability assigned to that sequence. On the right, we average the surprise of its individual symbols.

Define $Z_i=-\log p(X_i)$. The $Z_i$ are i.i.d., with

$$\mathbb{E}[Z_i]=-\sum _{x}p(x)\log p(x)=H(X).$$

The weak law of large numbers therefore gives the asymptotic equipartition property:

$$\boxed{-\frac{1}{n}\log p(X^n)\stackrel{\mathrm{Pr}}{\to }H(X).}$$

Explicitly, for every fixed $ϵ>0$,

$$\mathrm{Pr}\left(\left|-\frac{1}{n}\log p(X^n)-H(X)\right|>ϵ\right)⟶0.$$

The proof is short because the main idea is the change of variables: apply the law of large numbers to surprise, rather than to the source symbols themselves.

The name now has a precise meaning: asymptotic refers to long blocks, and equipartition refers to the nearly equal surprise per symbol of blocks that carry most of the probability. It does not make every possible block equally likely.

Problem 1: AEP-like limit

Problem. Let $X_1,X_2,\dots$ be i.i.d. drawn according to probability mass function $p(x)$. Does the following sequence converge in probability as $n\to \infty$? If so, what does it converge to?

$$(p(X_1,X_2,\dots ,X_n){)}^{1/n}.$$

Hint. You may use the Continuous Mapping Theorem in this and subsequent problems.

Solution.

The AEP gives $-\frac{1}{n}\log p(X^n)\stackrel{\mathrm{Pr}}{\to }H(X)$. Apply the continuous function $z\mapsto 2^{-z}$:

$$p(X^n{)}^{1/n}=2^{\frac{1}{n}\log p(X^n)}\stackrel{\mathrm{Pr}}{\to }{2}^{-H(X)}.$$

This is convergence of the probability’s $n$th root; the probability of a whole block generally becomes small as its length increases.

Problem 2: Repeated cake cuts

Problem. A cake is sliced roughly in half, the largest piece being chosen each time and the other pieces discarded. Assume that a random cut creates pieces of proportions

$$P=\{\begin{array}{ll}(2/3,1/3),& \text{with probability }1/4,\\ (2/5,3/5),& \text{with probability }3/4.\end{array}$$

For example, the first cut and choice of the largest piece may result in a piece of size $3/5$. Cutting and choosing from this piece might reduce its size to $(3/5)(2/3)$ at time 2, and so on. Roughly how large is the piece of cake after $n$ cuts?

Solution.

Assume successive cuts are independent, and let $R_i$ be the fraction retained at cut $i$: $2/3$ with probability $1/4$ and $3/5$ with probability $3/4$. If the starting size is one, $C_n={\prod }_{i=1}^n{R}_i$. Taking logarithms lets us use the law of large numbers:

$$\frac{1}{n}\log C_n\stackrel{\mathrm{Pr}}{\to }\frac{1}{4}\log \frac{2}{3}+\frac{3}{4}\log \frac{3}{5}.$$

Thus $C_n^{1/n}\stackrel{\mathrm{Pr}}{\to }(2/3{)}^{1/4}(3/5{)}^{3/4}\approx 0.6160$. The typical size decays like $(0.6160{)}^n$ on the logarithmic scale. This does not claim that $C_n/(0.6160{)}^n$ converges to one.

Problem 3: Geometric mean of a product

Problem. Let

$$X=\{\begin{array}{ll}1,& \text{with probability }1/2,\\ 2,& \text{with probability }1/4,\\ 3,& \text{with probability }1/4.\end{array}$$

Suppose $X_1,X_2,\dots$ are drawn i.i.d. according to this distribution. Find the limiting behavior in probability of the product

$$(X_1{X}_2\cdots X_n{)}^{1/n}.$$

Solution.

Average the logarithms, then exponentiate:

$$\frac{1}{n}\log (X_1\cdots X_n)\stackrel{\mathrm{Pr}}{\to }\mathbb{E}[\log X]=\frac{1}{4}\log 2+\frac{1}{4}\log 3.$$

Therefore $(X_1\cdots X_n{)}^{1/n}\stackrel{\mathrm{Pr}}{\to }{6}^{1/4}\approx 1.5651$. The geometric mean appears because the quantity being averaged is $\log X$, rather than $X$.

Problem 4: AEP with two probability models

Problem. Let $X_1,X_2,\dots$ be independent and identically distributed random variables drawn according to the probability mass function $p(x)$, where $x\in \{1,2,\dots ,m\}$. Thus

$$p(x_1,x_2,\dots ,x_n)=\prod _{i=1}^{n}p(x_i).$$

We know that $-\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)\to H(X)$ in probability. Let

$$q(x_1,x_2,\dots ,x_n)=\prod _{i=1}^{n}q(x_i),$$

where $q$ is another probability mass function on $\{1,2,\dots ,m\}$.

(a) Evaluate the limit in probability of $-\frac{1}{n}\log q(X_1,X_2,\dots ,X_n)$, where $X_1,X_2,\dots$ are i.i.d. $\sim p(x)$.

(b) Evaluate the limit in probability of the log-likelihood ratio

$$\frac{1}{n}\log \frac{q(X_1,\dots ,X_n)}{p(X_1,\dots ,X_n)},$$

when $X_1,X_2,\dots$ are i.i.d. $\sim p(x)$.

Solution.

If $q(x)>0$ whenever $p(x)>0$, the law of large numbers gives

$$-\frac{1}{n}\log q(X^n)\stackrel{\mathrm{Pr}}{\to }-\sum _{x}p(x)\log q(x)=H(X)+D(p\Vert q).$$

Subtracting the AEP limit for $p$ gives

$$\frac{1}{n}\log \frac{q(X^n)}{p(X^n)}\stackrel{\mathrm{Pr}}{\to }-D(p\Vert q).$$

Here $D(p\Vert q)={\sum }_{x}p(x)\log [p(x)/q(x)]$. The true distribution $p$ determines the averaging weights. See the coding interpretation of relative entropy.

If $p(x)>0$ but $q(x)=0$ for some symbol, a long block contains such a symbol with probability tending to one. The limits are then $+\infty$ and $-\infty$, respectively, in the extended sense.

2. The Typical Set

For $ϵ>0$, define the typical set

$$A_{ϵ}^{(n)}=\left\{x^n:\left|-\frac{1}{n}\log p(x^n)-H(X)\right|\le ϵ\right\}.$$

Equivalently, a sequence is typical when

$$\boxed{2^{-n(H(X)+ϵ)}\le p(x^n)\le 2^{-n(H(X)-ϵ)}.}$$

The AEP says $\mathrm{Pr}(X^n\in A_{ϵ}^{(n)})\to 1$. It does not say that most sequences are typical when we count every possible sequence equally. Probability mass and the number of sequences are different quantities.

2.1 Why typical sequences are “almost equiprobable”

Every typical sequence has normalized surprise within $ϵ$ of $H(X)$. This motivates the shorthand

$$p(x^n)\approx 2^{-nH(X)}.$$

The probability bounds specify what this approximation means: the normalized surprise of every typical sequence lies between $H(X)-ϵ$ and $H(X)+ϵ$.

2.2 How many typical sequences are there?

For sufficiently large $n$, the AEP gives $\mathrm{Pr}(A_{ϵ}^{(n)})>1-ϵ$. Combining this with the probability bounds gives

$$\boxed{(1-ϵ)2^{n(H(X)-ϵ)}\le |A_{ϵ}^{(n)}|\le 2^{n(H(X)+ϵ)}.}$$

Proof of the cardinality bounds

Each typical sequence has probability at least $2^{-n(H(X)+ϵ)}$. Thus

$$1\ge \sum _{x^n\in A_{ϵ}^{(n)}}p(x^n)\ge |A_{ϵ}^{(n)}|2^{-n(H(X)+ϵ)},$$

proving the upper bound. For the lower bound, use the upper probability bound for each sequence:

$$1-ϵ\le \sum _{x^n\in A_{ϵ}^{(n)}}p(x^n)\le |A_{ϵ}^{(n)}|2^{-n(H(X)-ϵ)}.$$

The upper bound holds for every $n$; the lower bound requires sufficiently large $n$.

The typical set has probability close to one, its sequences have probabilities close to $2^{-nH(X)}$ on the exponential scale, and its size is bounded by exponents near $nH(X)$. These three properties make it useful for coding.

Problem 5: Counting a high-probability set

Problem. A discrete memoryless source emits a sequence of statistically independent binary digits with probabilities $p(1)=0.005$ and $p(0)=0.995$. The digits are taken 100 at a time, and a binary codeword is provided for every sequence of 100 digits containing three or fewer ones.

(a) Assuming that all codewords are the same length, find the minimum length required to provide codewords for all sequences with three or fewer ones.

(b) Calculate the probability of observing a source sequence for which no codeword has been assigned.

Solution.

A block with exactly $k$ ones can place those ones in $\left(\genfrac{}{}{0ex}{}{100}{k}\right)$ positions. Thus the selected set $S=\{x^{100}:\text{at most three ones}\}$ has size

$$|S|=\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)=1+100+4950+161700=166751.$$

For part (a), distinct labels of length $l$ require $2^l\ge |S|$. Hence $l=\lceil \log 166751\rceil =18$ bits.

For part (b), the number of ones is $K\sim \mathrm{Binomial}(100,0.005)$, so

$$\mathrm{Pr}(K>3)=1-\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)(0.005{)}^k(0.995{)}^{100-k}\approx \mathrm{0.00167327.}$$

This illustrates the difference between cardinality and probability: 166751 blocks out of $2^{100}$ possibilities carry about 99.833% of the probability. $S$ is a high-probability set defined by a count cutoff, rather than the two-sided typicality criterion.

3. A Biased-Coin Example

Consider a Bernoulli source. Let $X_i\sim \mathrm{Bernoulli}(p)$ and write $q=1-p$. A particular block containing $k$ ones has probability

$$p(x^n)=p^k{q}^{n-k}.$$

Its probability depends on the number of ones, not their positions. With high probability, the proportion of ones is close to $p$. The normalized surprise is then close to the binary entropy

$$H(p)=-p\log p-q\log q,$$

and these typical sequences have probabilities near $2^{-nH(p)}$.

Now take $p=0.9$. The typical sequences have a proportion of ones close to 0.9. The most likely individual sequence, however, is the all-ones sequence. It falls outside a sufficiently narrow typical band.

This distinction matters: the most likely individual outcome need not belong to the collection of outcomes that carries most of the probability. We will use this distinction to compare typical sets with the smallest high-probability sets.

Problem 5: Probability of a biased-coin count range

Problem. A discrete memoryless source emits a sequence of statistically independent binary digits with probabilities $p(1)=0.005$ and $p(0)=0.995$. The digits are taken 100 at a time, and a binary codeword is provided for every sequence of 100 digits containing three or fewer ones.

(a) Assuming that all codewords are the same length, find the minimum length required to provide codewords for all sequences with three or fewer ones.

(b) Calculate the probability of observing a source sequence for which no codeword has been assigned.

Solution.

For a particular block with $k$ ones,

$$p(x^{100})=(0.005{)}^k(0.995{)}^{100-k}.$$

There are $\left(\genfrac{}{}{0ex}{}{100}{k}\right)$ such blocks. To find the total probability of a count, multiply the probability of one block by the number of blocks with that count.

For part (a), ${\sum }_{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)=166751$, so the minimum length is $\lceil \log 166751\rceil =18$ bits.

For part (b), add the probabilities of all excluded counts:

$$\mathrm{Pr}(K>3)=\sum _{k=4}^{100}\left(\genfrac{}{}{0ex}{}{100}{k}\right)(0.005{)}^k(0.995{)}^{100-k}\approx \mathrm{0.00167327.}$$

Here $K$ is binomial with parameters 100 and 0.005. The selected count range has probability about 0.99832673. This calculation shows why the probability of one sequence and the probability of a whole collection must be distinguished.

4. Why AEP Enables Compression

If both encoder and decoder know $p$, $n$, and $ϵ$, they can agree on an ordering of the typical set. A typical sequence can then be represented by its index, requiring at most

$$\lceil n(H(X)+ϵ)\rceil$$

bits. This is the operational meaning of the typical-set size bound.

To encode every possible block, we need to handle both typical and atypical sequences. Use a leading flag bit to distinguish two cases:

Input block	Encoding
Typical	0 followed by its fixed-width typical-set index
Atypical	1 followed by a fixed-width index in the atypical set

The decoder reads the flag, then knows how many bits to read. The mapping is one-to-one and reconstructs every block exactly.

Allowing for the flag and rounding, typical codewords have length at most $n(H(X)+ϵ)+2$. Atypical codewords have length at most $n\log |\mathcal{X}|+2$, because there are no more than $|\mathcal{X}{|}^n$ atypical blocks.

For sufficiently large $n$, $\mathrm{Pr}(X^n\notin A_{ϵ}^{(n)})\le ϵ$. Splitting the expected codeword length between the two sets gives

$$\begin{array}{rl}\mathbb{E}[l(X^n)]& \le \mathrm{Pr}(A_{ϵ}^{(n)})[n(H(X)+ϵ)+2]\\ & +\mathrm{Pr}((A_{ϵ}^{(n)}{)}^c)[n\log |\mathcal{X}|+2]\\ & \le n(H(X)+ϵ)+ϵn\log |\mathcal{X}|+2.\end{array}$$

Thus

$$\frac{\mathbb{E}[l(X^n)]}{n}\le H(X)+ϵ+ϵ\log |\mathcal{X}|+\frac{2}{n}.$$

First choose $ϵ$ small, then choose $n$ large. The terms beyond $H(X)$ can be made arbitrarily small. Consequently, for any positive rate tolerance, sufficiently long i.i.d. blocks have a one-to-one binary code whose expected bits per symbol are at most entropy plus that tolerance.

The essential idea is that typical sequences receive short descriptions of approximately $nH(X)$ bits. Atypical sequences may receive longer descriptions, but their small total probability keeps their contribution to the average small.

Problem 5: Encoding blocks with at most three ones

Problem. A discrete memoryless source emits a sequence of statistically independent binary digits with probabilities $p(1)=0.005$ and $p(0)=0.995$. The digits are taken 100 at a time, and a binary codeword is provided for every sequence of 100 digits containing three or fewer ones.

(a) Assuming that all codewords are the same length, find the minimum length required to provide codewords for all sequences with three or fewer ones.

(b) Calculate the probability of observing a source sequence for which no codeword has been assigned.

Solution.

There are

$$M=\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)=1+100+4950+161700=166751$$

eligible blocks. Distinct fixed-length binary labels require $2^l\ge M$, so $l=\lceil \log M\rceil =18$ bits.

If $K$ counts ones, then $K\sim \mathrm{Binomial}(100,0.005)$. The probability of having no assigned codeword is

$$\mathrm{Pr}(K>3)=1-\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)(0.005{)}^k(0.995{)}^{100-k}\approx \mathrm{0.00167327.}$$

Thus the selected set covers about 99.833% of the probability. It is a high-probability set selected by a count cutoff; it is not defined by the two-sided typical-set criterion. Unlike the flag construction, this code leaves some blocks unencoded.

5. Could a Much Smaller Set Carry the Same Probability?

The typical set is one way to capture most of the probability, but it need not be the smallest such set. Could a better choice change the exponential size?

Let $B_{\delta }^{(n)}$ be a smallest set of blocks satisfying

$$\mathrm{Pr}(X^n\in B_{\delta }^{(n)})\ge 1-\delta .$$

The lower bound is as follows: for $0<\delta <1/2$ and any ${\delta }^{\prime }>0$, a set with probability greater than $1-\delta$ satisfies

$$\boxed{\frac{1}{n}\log |B_{\delta }^{(n)}|>H(X)-{\delta }^{\prime }}$$

for sufficiently large $n$. To see why, note that the typical set has probability approaching one. Any set with probability greater than $1-\delta$ must therefore share substantial probability with it. Each sequence in that intersection has probability at most $2^{-n(H(X)-ϵ)}$, so carrying that shared probability requires exponentially many sequences.

The typical set has size between exponents near $nH(X)$, and a smallest high-probability set cannot have a substantially smaller exponent. We express this using equality to first order in the exponent:

$$a_n\doteq b_n⟺\underset{n\to \infty }{\lim }\frac{1}{n}\log \frac{a_n}{b_n}=0.$$

For a fixed $0<\delta <1/2$, the smallest-set result is

$$\boxed{|B_{\delta }^{(n)}|\doteq 2^{nH(X)}.}$$

The two sets can nevertheless differ in membership. For the Bernoulli source with parameter 0.9, a smallest high-probability set is obtained by taking the most probable individual sequences first, including all ones. The typical set instead selects sequences whose proportion of ones is close to 0.9. Their different selection rules still lead to the same leading entropy exponent as the typicality tolerance is made small.

Entropy therefore connects three quantities: the surprise per symbol of a long random block, the exponential size of a high-probability set, and the average number of bits needed to describe a block.

Problem 5: Selecting the most probable blocks

Problem. A discrete memoryless source emits a sequence of statistically independent binary digits with probabilities $p(1)=0.005$ and $p(0)=0.995$. The digits are taken 100 at a time, and a binary codeword is provided for every sequence of 100 digits containing three or fewer ones.

(a) Assuming that all codewords are the same length, find the minimum length required to provide codewords for all sequences with three or fewer ones.

(b) Calculate the probability of observing a source sequence for which no codeword has been assigned.

Solution.

For part (a), the selected set $S$ has ${\sum }_{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)=166751$ blocks, requiring $\lceil \log 166751\rceil =18$ bits per label.

For part (b), its missing probability is

$$\delta =1-\sum _{k=0}^3\left(\genfrac{}{}{0ex}{}{100}{k}\right)(0.005{)}^k(0.995{)}^{100-k}\approx 0.00167327,$$

so $\mathrm{Pr}(S)=1-\delta \approx 0.99832673$.

The probability of an individual block decreases with its number of ones: increasing that count by one multiplies its probability by $0.005/0.995<1$. Thus $S$ contains the most probable individual blocks, down to the cutoff of three ones.

This makes $S$ a smallest-cardinality set for this exact coverage target. Any set with fewer than $|S|$ elements has total probability at most that of the $|S|-1$ most probable blocks, which is strictly below $\mathrm{Pr}(S)$. This is a finite-block illustration of selecting a smallest high-probability set; the asymptotic result above describes its leading size as block length grows with a fixed probability target.

6. Takeaways

• Average surprise becomes predictable. For i.i.d. symbols, $-\frac{1}{n}\log p(X^n)$ converges in probability to $H(X)$.
• Typicality concerns total probability. The typical set carries almost all the probability, even though a particular typical sequence can be very unlikely. The most likely individual sequence need not be typical.
• Entropy controls the number of descriptions. Typical-set size is bounded by exponents near $nH(X)$, so a typical block needs about $nH(X)$ bits to identify.
• Compression guarantees matter. The flag construction recovers every block exactly and approaches entropy in expected bits per symbol. Problem 5 instead uses fixed-length labels for a selected set and leaves a small probability of unencoded blocks.
• For products, take logarithms first. Problems 1–4 turn multiplicative quantities into averages, apply the law of large numbers, and transform back when needed.