The Asymptotic Equipartition Property (AEP) and Strongly Typical Sequences

Intuition Beginner

Imagine flipping a fair coin 100 times. There are $2^{100}$ possible sequences of heads and tails. That is an astronomically large number. But almost all of those sequences look boring: roughly 50 heads and 50 tails, in some order. The sequences that are "surprising" — all heads, or alternating HTHTHT... — are vanishingly rare.

The asymptotic equipartition property (AEP) makes this precise. It says that when you draw $n$ independent samples from any distribution, the resulting sequence almost certainly lands in a small collection called the typical set. Each sequence in the typical set has approximately the same probability, close to $2^{-nH}$, where $H$ is the entropy of one draw. The typical set is tiny compared to the full space of all possible sequences, yet it carries almost all the probability.

Think of it this way. The full space of 100 coin flips has $2^{100}$ elements. The typical set has about $2^{100H}$ elements, where $H\le 1$ is the entropy per flip. For a fair coin, $H=1$ and the typical set is most of the space. For a biased coin with $H=0.5$, the typical set is only about $2^{50}$ out of $2^{100}$ — exponentially smaller, yet still carrying nearly all the probability mass.

This is why data compression works. You only need to give distinct labels (codewords) to the sequences in the typical set. Since the typical set has about $2^{nH}$ elements, you need about $nH$ bits to label them all. The remaining sequences are so unlikely that you can afford to give them all the same default label, at negligible cost. The AEP is the theorem that justifies this strategy: it tells you the typical set exists, how big it is, and that it carries nearly all the probability.

Visual Beginner

Figure: a bar chart showing all $2^4=16$ binary sequences of length 4 drawn from a biased coin with $p=0.7$ for heads. The x-axis lists the 16 sequences. The y-axis shows probability. A horizontal band highlights the typical set: sequences with 1 to 3 heads (the ones whose per-symbol log-probability is close to $H\approx 0.88$ bits). The atypical sequences (all heads, all tails) sit far outside the band.

| Sequence length $n$ | Alphabet size $|\mathcal{X}|$ | Full space $|\mathcal{X}{|}^n$ | Typical set size $\approx 2^{nH}$ | Ratio | |---|---|---|---|---| | Fair coin, $n=10$ | 2 | $2^{10}=1024$ | $\approx 2^{10}=1024$ | $\approx 1$ (entropy = 1, almost everything is typical) | | Biased coin ($p=0.9$), $n=10$ | 2 | $2^{10}=1024$ | $\approx 2^{4.7}\approx 26$ | 0.025 | | Fair die, $n=10$ | 6 | $6^{10}\approx 10^{7.8}$ | $\approx 2^{25.8}\approx 10^{7.8}$ | $\approx 1$ | | Loaded die, $n=100$ | 6 | $6^{100}\approx 10^{77.8}$ | $\approx 2^{214}\approx 10^{64.4}$ | $\approx 10^{-13.4}$ |

The pattern: the gap between the full space and the typical set grows exponentially with $n$. For a source with entropy less than the maximum, nearly all sequences are atypical, yet the atypical ones collectively carry almost no probability.

Worked example Beginner

A biased coin lands heads with probability $p=0.7$ and tails with probability $q=0.3$. The entropy is $H=-0.7{\log }_{2}0.7-0.3{\log }_{2}0.3\approx 0.360+0.521=0.881$ bits. We flip the coin $n=4$ times.

The probability of any specific sequence $x^4=(x_1,x_2,x_3,x_4)$ is $p(x^4)=0.7^k\cdot 0.3^{4-k}$ where $k$ is the number of heads. The per-symbol log-probability is $-(1/4){\log }_{2}p(x^4)=(k/4){\log }_2(1/0.7)+((4-k)/4){\log }_2(1/0.3)$.

Step 1. Compute $-(1/n){\log }_{2}p(x^n)$ for each possible number of heads:

• $k=4$ (HHHH): $-(1/4){\log }_2(0.7^4)={\log }_2(1/0.7)\approx 0.515$ bits. Far from $H=0.881$.
• $k=3$ (e.g., HHHT): $-(1/4){\log }_2(0.7^3\cdot 0.3)=(3/4)(0.515)+(1/4)(1.737)\approx 0.820$ bits. Close to $H$.
• $k=2$ (e.g., HHTT): $-(1/4){\log }_2(0.7^2\cdot 0.3^2)=(2/4)(0.515)+(2/4)(1.737)=1.126$ bits. Less close.
• $k=1$ (e.g., HTTT): $-(1/4){\log }_2(0.7\cdot 0.3^3)\approx 1.433$ bits. Far.
• $k=0$ (TTTT): ${\log }_2(1/0.3)\approx 1.737$ bits. Far.

Step 2. Choose $ϵ=0.3$. The typical set is $A_{ϵ}^{(4)}=\{x^4:|-(1/4){\log }_{2}p(x^4)-0.881|<0.3\}$. The interval is $(0.581,1.181)$. Sequences with $k=3$ (per-symbol info $\approx 0.820$) and $k=2$ (per-symbol info $\approx 1.126$) fall in the typical set.

Step 3. Count and weigh. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ sequences with $k=3$ and $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ with $k=2$, giving $|A_{ϵ}^{(4)}|=10$. The full space has $2^4=16$ sequences. The probability of the typical set is $P(k=3)+P(k=2)=\left(\genfrac{}{}{0ex}{}{4}{3}\right)0.7^3\cdot 0.3+\left(\genfrac{}{}{0ex}{}{4}{2}\right)0.7^2\cdot 0.3^2=4(0.343)(0.3)+6(0.49)(0.09)=0.4116+0.2646=0.6762$.

With only $n=4$ the concentration is weak — $P(A_{ϵ})\approx 0.68$, not yet close to 1. As $n$ grows, the law of large numbers forces $P(A_{ϵ}^{(n)})\to 1$ for any fixed $ϵ>0$, and the typical set size concentrates near $2^{nH}$.

Check your understanding Beginner

Formal definition Intermediate+

Let $X_1,X_2,\dots ,X_n$ be drawn i.i.d. from a distribution $p(x)$ on a finite alphabet $\mathcal{X}$ with entropy $H(X)=-{\sum }_{x\in \mathcal{X}}p(x)\log p(x)$. Write $X^n=(X_1,\dots ,X_n)$ and $x^n=(x_1,\dots ,x_n)$ for a specific realisation.

Definition (Information per symbol). The per-symbol log-likelihood of a sequence $x^n$ is

$$-\frac{1}{n}\log p(x^n)=-\frac{1}{n}\sum _{i=1}^n\log p(x_i),$$

where the product form $p(x^n)={\prod }_{i=1}^{n}p(x_i)$ follows from independence.

Definition (Typical set). For $ϵ>0$ and positive integer $n$, the typical set is

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

Equivalently, $x^n\in A_{ϵ}^{(n)}$ if and only if

$$2^{-n(H+ϵ)}<p(x^n)<2^{-n(H-ϵ)}.$$

Counterexamples to common slips

• The typical set is not the set of high-probability sequences. The highest-probability sequence is the mode of the product distribution, which for a biased coin is all-heads. The typical set excludes the mode when $H<{\log }_2|\mathcal{X}|$. The typical set contains sequences whose per-symbol information is near $H$, not those with highest absolute probability.

• Typicality does not require the sequence to "look random." For a uniform distribution on $\mathcal{X}$, every sequence is typical. For a highly biased distribution, a typical sequence still has most symbols equal to the most likely value — that is exactly what the entropy predicts.

• The typical set is not uniquely defined. It depends on the choice of $ϵ$ and $n$. Different $ϵ$ give different sets. The theorem says that for any fixed $ϵ$, the typical set eventually (for large enough $n$) captures most of the probability.

Key theorem with proof Intermediate+

Theorem (AEP). Let $X_1,X_2,\dots$ be drawn i.i.d. from a distribution $p$ with entropy $H(X)$. Then

$$-\frac{1}{n}\log p(X^n)⟶H(X)\text{in probability},$$

i.e., for every $ϵ>0$,

$$\mathrm{Pr}\left[\left|-\frac{1}{n}\log p(X^n)-H(X)\right|\ge ϵ\right]⟶0\text{as }n\to \infty .$$

Proof. Since $X_1,X_2,\dots$ are i.i.d., the random variables $Y_i=-\log p(X_i)=\log (1/p(X_i))$ are also i.i.d. The expected value is

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

The per-symbol log-probability is the sample mean:

$$-\frac{1}{n}\log p(X^n)=\frac{1}{n}\sum _{i=1}^n{Y}_i={\bar{Y}}_n.$$

Since the $Y_i$ are i.i.d. with finite mean $H(X)$ (finiteness follows from $H(X)\le \log |\mathcal{X}|<\infty$ for finite alphabets), the weak law of large numbers 37.02.01 gives ${\bar{Y}}_n\to H(X)$ in probability. This is exactly the AEP. $\square$

Theorem (Properties of the typical set). For any $ϵ>0$:

1. Probability bound. For $n$ sufficiently large, $\mathrm{Pr}[X^n\in A_{ϵ}^{(n)}]>1-ϵ$.

2. Cardinality upper bound. $|A_{ϵ}^{(n)}|\le 2^{n(H+ϵ)}$.

3. Cardinality lower bound. For $n$ sufficiently large, $|A_{ϵ}^{(n)}|\ge (1-ϵ)2^{n(H-ϵ)}$.

Proof of (1). By the AEP, $-\frac{1}{n}\log p(X^n)\to H$ in probability. For any $ϵ>0$, there exists $n_0$ such that for all $n\ge n_0$:

$$\mathrm{Pr}\left[\left|-\frac{1}{n}\log p(X^n)-H\right|\ge ϵ\right]<ϵ.$$

Taking complements: $\mathrm{Pr}[X^n\in A_{ϵ}^{(n)}]>1-ϵ$.

Proof of (2). For any $x^n\in A_{ϵ}^{(n)}$, we have $p(x^n)>2^{-n(H+ϵ)}$. Since the total probability of $A_{ϵ}^{(n)}$ is at most 1:

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

giving $|A_{ϵ}^{(n)}|<2^{n(H+ϵ)}$.

Proof of (3). For $n$ sufficiently large, $\mathrm{Pr}[X^n\in A_{ϵ}^{(n)}]>1-ϵ$. Also, for any $x^n\in A_{ϵ}^{(n)}$, $p(x^n)<2^{-n(H-ϵ)}$. Therefore:

$$1-ϵ<\mathrm{Pr}[X^n\in A_{ϵ}^{(n)}]=\sum _{x^n\in A_{ϵ}^{(n)}}p(x^n)<|A_{ϵ}^{(n)}|\cdot 2^{-n(H-ϵ)},$$

giving $|A_{ϵ}^{(n)}|>(1-ϵ)2^{n(H-ϵ)}$. $\square$

Bridge. The AEP builds toward the source coding theorem in 46.02.02 by establishing that only $2^{nH}$ codewords are needed to describe $n$ symbols with negligible error probability, making $H$ the operational compression limit. It appears again in the channel coding theorem 46.03.01 where joint typicality between input and output sequences replaces single-sequence typicality, and the mutual information $I(X;Y)$ replaces $H(X)$ as the governing exponent. The foundational reason the AEP works is the law of large numbers applied to the information random variables $Y_i=\log (1/p(X_i))$, which has expected value $H(X)$; this is exactly the mechanism by which the chain rule from 46.01.01 telescopes the information content of a sequence into a sum of independent terms. The AEP generalises to the method of types and large deviations 37.07.05, where the exponent for atypical behaviour is the relative entropy $D(q\Vert p)$; the central insight is that entropy governs not just average uncertainty but the geometry of the probability landscape — the typical set is an exponentially small subset of the full space that carries nearly all the mass.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib provides the weak law of large numbers for i.i.d. integrable random variables (ProbabilityTheory.lawOfLargeNumbers) and the basic PMF type for discrete distributions. However, it does not define the typical set $A_{ϵ}^{(n)}$ as a measurable set indexed by $ϵ$ and $n$, nor does it prove the AEP theorem that $-(1/n)\log p(X^n)\to H(X)$ in probability. The cardinality bounds $(1-ϵ)2^{n(H-ϵ)}\le |A_{ϵ}|\le 2^{n(H+ϵ)}$ are absent. Strong typicality — the refinement where individual letter frequencies are controlled — is not formalised. The foundational gap is the convergence-in-probability statement for the empirical entropy of an i.i.d. sequence, plus the combinatorial bounds on the typical set. A Codex.InformationTheory.AEP module proving the AEP from the law of large numbers and deriving the cardinality bounds would be the load-bearing step; this unit ships without it.

Advanced results Master

Strong typicality and the method of types

The weak AEP uses convergence in probability of $-(1/n)\log p(X^n)$ to $H$. Strong typicality refines this by controlling the empirical distribution (the type) of each sequence individually.

Definition (Type). For a sequence $x^n\in {\mathcal{X}}^n$, the type (or empirical distribution) is $\pi (a|x^n)=N(a|x^n)/n$, where $N(a|x^n)$ is the number of times symbol $a$ appears in $x^n$.

Definition (Strongly typical set). For $ϵ>0$, the strongly typical set is

$$T_{ϵ}^{(n)}=\left\{x^n\in {\mathcal{X}}^n:\forall a\in \mathcal{X},\left|\pi (a|x^n)-p(a)\right|\le \frac{ϵ}{|\mathcal{X}|}\right\}.$$

Strong typicality implies weak typicality: if $x^n\in T_{ϵ}^{(n)}$ then $x^n\in A_{{ϵ}^{\prime }}^{(n)}$ for ${ϵ}^{\prime }=ϵ\cdot C/|\mathcal{X}|$ where $C={\sum }_a\log (1/p(a))$ (proved in the exercises). The converse is false: a sequence can have the right per-symbol log-probability without having the right letter frequencies.

The strong version is needed for proving the channel coding theorem and the rate-distortion theorem. In the channel coding setting, the joint typicality of input-output pairs $(x^n,y^n)$ requires that both marginals and the joint type are close to their expected distributions, which weak typicality cannot guarantee.

Theorem (Size of the type class). For a type $\pi$ with $\pi (a)=n_a/n$ for integers $n_a$, the number of sequences with type $\pi$ is

$$|T_{\pi }|=\left(\genfrac{}{}{0ex}{}{n}{n_{a_1},n_{a_2},\dots ,n_{a_k}}\right)=\frac{n!}{{\prod }_{a\in \mathcal{X}}{n}_a!}.$$

By Stirling's approximation, $|T_{\pi }|\approx 2^{nH(\pi )}$, where $H(\pi )$ is the entropy of the type class distribution. This gives the method-of-types bound: the number of types is polynomial in $n$ (at most $(n+1{)}^{|\mathcal{X}|}$), while the number of sequences in each type class is exponential with exponent $H(\pi )$.

The high-probability set and its optimality

The typical set is one convenient high-probability set, but is it the smallest? The answer is: up to polynomial factors, yes.

Theorem (Size of the smallest high-probability set). Define $S^{(n)}(\delta )$ to be the smallest subset of ${\mathcal{X}}^n$ with $\mathrm{Pr}[X^n\in S^{(n)}]\ge 1-\delta$. Then for any $\delta \in (0,1)$ and $ϵ>0$, for $n$ sufficiently large:

$$(1-\delta -ϵ)2^{n(H-ϵ)}\le |S^{(n)}(\delta )|\le 2^{n(H+ϵ)}.$$

Proof sketch. The upper bound follows from the fact that the typical set $A_{ϵ}^{(n)}$ is a high-probability set with size at most $2^{n(H+ϵ)}$. The lower bound: any set with probability $\ge 1-\delta$ must contain at least $(1-\delta -ϵ)2^{n(H-ϵ)}$ typical sequences (since the atypical sequences contribute at most $ϵ$ probability), and each typical sequence has probability at most $2^{-n(H-ϵ)}$. $\square$

This means the typical set is near-optimal: no other high-probability set can be substantially smaller. The exponent $nH$ is intrinsic to the source, not an artifact of the typical-set construction.

Convergence rates

The AEP is a qualitative result (convergence in probability). Quantitative bounds come from large deviations. By the Chernoff bound applied to $Y_i=\log (1/p(X_i))$:

$$\mathrm{Pr}\left[\left|-\frac{1}{n}\log p(X^n)-H\right|\ge ϵ\right]\le 2\exp \left(-\frac{n{ϵ}^2}{2{\sigma }^2}\right),$$

where ${\sigma }^2=\text{Var}(\log (1/p(X)))$ is the varentropy. The varentropy governs the rate of concentration: it measures how spread out the information content is around its mean. For a fair coin, ${\sigma }^2=0$ (since $Y_i$ is deterministic at 1 bit); for a biased coin, ${\sigma }^2>0$ and grows as the bias increases.

The AEP for stationary ergodic sources

The AEP extends beyond i.i.d. sources. For a stationary ergodic source $(X_i{)}_{i=1}^{\infty }$ with entropy rate $\mathcal{H}={\lim }_{n\to \infty }(1/n)H(X_1,\dots ,X_n)$, the Shannon-McMillan-Breiman theorem states:

$$-\frac{1}{n}\log p(X_1,\dots ,X_n)\to \mathcal{H}\text{a.s.}$$

This is an almost-sure convergence, stronger than the convergence in probability for the i.i.d. case. The proof uses the ergodic theorem (Birkhoff or the martingale convergence theorem applied to the conditional densities). For i.i.d. sources, $\mathcal{H}=H(X_1)$ and the SMB theorem reduces to the strong law of large numbers.

Synthesis. The AEP is the foundational reason entropy has operational meaning; the typical set of size $\approx 2^{nH}$ is near-optimal among all high-probability sets, and the source coding theorem 46.02.02 formalises this as a compression limit of $H$ bits per symbol. Strong typicality refines the picture by controlling individual letter frequencies, which builds toward the channel coding theorem 46.03.01 where joint typicality between input and output sequences is the central tool. The varentropy governs the convergence rate, connecting to large deviations 37.07.05 where the exponent for atypical events is the relative entropy $D(q\Vert p)$. The central insight is that entropy is not merely an average — it is the exponent governing the geometry of high-dimensional probability distributions, and the AEP makes this precise by showing that the effective support of $n$ draws is a set of size $2^{nH}$, exponentially smaller than the full space $|\mathcal{X}{|}^n$ whenever $H<\log |\mathcal{X}|$.

Full proof set Master

Proposition (Strong typicality implies weak typicality). Let $T_{ϵ}^{(n)}$ be the strongly typical set and $A_{{ϵ}^{\prime }}^{(n)}$ the weakly typical set. Then $T_{ϵ}^{(n)}\subseteq A_{{ϵ}^{\prime }}^{(n)}$ where ${ϵ}^{\prime }=ϵ{\max }_a\log (1/p(a))$.

Proof. For any $x^n\in T_{ϵ}^{(n)}$, define $\nu (a)=N(a|x^n)/n$. By strong typicality, $|\nu (a)-p(a)|\le ϵ$ for each $a\in \mathcal{X}$. Compute:

$$\begin{array}{rl}\left|-\frac{1}{n}\log p(x^n)-H\right|& =\left|\sum _a\nu (a)\log \frac{1}{p(a)}-\sum _{a}p(a)\log \frac{1}{p(a)}\right|\\ & =\left|\sum _a(\nu (a)-p(a))\log \frac{1}{p(a)}\right|\\ & \le \sum _a|\nu (a)-p(a)|\cdot \log \frac{1}{p(a)}\\ & \le ϵ\sum _a\log \frac{1}{p(a)}\\ & \le ϵ\cdot |\mathcal{X}|\cdot \underset{a}{\max }\log \frac{1}{p(a)}.\end{array}$$

Setting ${ϵ}^{\prime }=ϵ|\mathcal{X}|{\max }_a\log (1/p(a))$ gives the result. For the refined bound with $ϵ/|\mathcal{X}|$ per symbol, the same argument with $|\nu (a)-p(a)|\le ϵ/|\mathcal{X}|$ yields ${ϵ}^{\prime }=ϵ{\max }_a\log (1/p(a))$. $\square$

Proposition (Number of types). The number of distinct types for sequences of length $n$ from an alphabet of size $|\mathcal{X}|=m$ is at most $(n+1{)}^m$.

Proof. A type is determined by the counts $N(a)=n_a$ for each $a\in \mathcal{X}$, subject to ${\sum }_a{n}_a=n$ with each $n_a\ge 0$. The number of such integer tuples is $\left(\genfrac{}{}{0ex}{}{n+m-1}{m-1}\right)\le (n+1{)}^{m-1}\le (n+1{)}^m$. Each tuple defines at most one type, so the total number of types is at most $(n+1{)}^m$. $\square$

Proposition (Probability of a type class). For any type $\pi$ with counts $n_a/n$, the probability that an i.i.d. sequence has type $\pi$ satisfies

$$\frac{1}{(n+1{)}^m}{2}^{-nD(\pi \Vert p)}\le \mathrm{Pr}[\text{type of }{X}^n=\pi ]\le 2^{-nD(\pi \Vert p)},$$

where $D(\pi \Vert p)={\sum }_a\pi (a)\log (\pi (a)/p(a))$ is the KL divergence.

Proof. The probability of any specific sequence with type $\pi$ is ${\prod }_{a}p(a{)}^{n_a}=2^{-n{\sum }_a\pi (a)\log (1/p(a))}$. The number of sequences with type $\pi$ is the multinomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{n_{a_1},\dots ,n_{a_m}}\right)=2^{nH(\pi )}/\Theta (\text{polynomial})$ by Stirling. Therefore:

$$\mathrm{Pr}[\text{type}=\pi ]=\left(\genfrac{}{}{0ex}{}{n}{n_{a_1},\dots ,n_{a_m}}\right)\prod _{a}p(a{)}^{n_a}=2^{nH(\pi )}\cdot 2^{-n{\sum }_a\pi (a)\log (1/p(a))}\cdot \Theta (\text{poly}{)}^{-1}.$$

Since ${\sum }_a\pi (a)\log (1/p(a))=H(\pi )+D(\pi \Vert p)$, this simplifies to $2^{-nD(\pi \Vert p)}\cdot \Theta (\text{poly}{)}^{-1}$. The polynomial factors are bounded by $(n+1{)}^m$, giving the stated bounds. $\square$

Connections Master

• 46.01.01 — The AEP uses the entropy $H(X)=\mathbb{E}[\log (1/p(X))]$ defined in that unit, and the chain rule to decompose $-\log p(X^n)={\sum }_i\log (1/p(X_i))$ into i.i.d. terms for the law-of-large-numbers argument.
• 37.02.01 — The weak law of large numbers is the engine of the AEP; the convergence $-(1/n)\log p(X^n)\to H$ is an application of the WLLN to the information random variables $Y_i=\log (1/p(X_i))$.
• 46.02.02 — Shannon's source coding theorem uses the AEP to prove that $H$ bits per symbol suffice for compression; the typical set of size $\approx 2^{nH}$ is the set that the optimal code must be able to index.
• 46.03.01 — The channel coding theorem extends the AEP to joint typicality of input-output pairs $(X^n,Y^n)$, replacing $H(X)$ with $I(X;Y)$ as the governing exponent.
• 46.01.02 — The relative entropy $D(p\Vert q)$ measures the exponent for "q-typical" sets under distribution $p$; the AEP is the $q=p$ case where $D=0$.
• 37.07.05 — Sanov's theorem in large deviations gives the precise exponential rate for atypical types as $2^{-nD(\pi \Vert p)}$; the method of types developed here is the combinatorial engine behind Sanov's theorem.

Historical & philosophical context Master

The AEP has its roots in Shannon's 1948 paper "A Mathematical Theory of Communication" (Bell System Technical Journal 27, 379-423 and 623-656). In Section 7, Shannon argued informally that long sequences from a discrete source fall into two classes: a relatively small number of high-probability sequences and a vast number of low-probability ones. He used this to derive the source coding theorem, though he did not formally define the typical set or prove the AEP as a separate theorem.

The formal AEP theorem and the definition of the typical set $A_{ϵ}^{(n)}$ appeared in the information-theory textbook tradition through the 1960s and 1970s. Cover and Thomas (1991, 2nd edition 2006) gave the standard presentation in their Chapter 3, proving the AEP from the weak law of large numbers and deriving the cardinality and probability bounds.

Strong typicality was introduced independently by Wolfowitz (1961, Coding Theorems of Information Theory) and developed systematically by Csiszar and Korner (1981, Information Theory: Coding Theorems for Discrete Memoryless Systems). The method of types — the combinatorial framework for counting sequences by their empirical distributions — is due to Csiszar, who used it to give elegant proofs of the channel coding theorem, the rate-distortion theorem, and Sanov's theorem. The key insight of the method of types is that the number of types is polynomial in $n$, while each type class is exponential, so the combinatorics simplify dramatically.

The Shannon-McMillan-Breiman theorem extends the AEP from i.i.d. sources to stationary ergodic sources. Shannon (1948) stated the result for Markov chains. McMillan (1953, "The Basic Theorems of Information Theory") proved convergence in probability for stationary ergodic sources. Breiman (1957, "The Individual Ergodic Theorem of Information Theory") proved almost-sure convergence. The SMB theorem is one of the deepest results in ergodic theory and information theory, connecting the entropy rate of a process to the asymptotic behaviour of its sample paths.

The varentropy — the variance of the information random variable $\log (1/p(X))$ — governs the convergence rate of the AEP. Kontoyiannis and Verdu (2014, "Optimal Exponent for the AEP") showed that the varentropy determines the precise exponent in the large-deviation probability of the atypical event, sharpening the qualitative AEP to a quantitative bound.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@book{wolfowitz1961,
  author    = {Wolfowitz, J.},
  title     = {Coding Theorems of Information Theory},
  publisher = {Springer},
  year      = {1961},
}
@article{mcmillan1953,
  author  = {McMillan, B.},
  title   = {The Basic Theorems of Information Theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {25},
  pages   = {241--252},
  year    = {1953},
}
@article{breiman1957,
  author  = {Breiman, L.},
  title   = {The Individual Ergodic Theorem of Information Theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {28},
  pages   = {809--811},
  year    = {1957},
}
@article{kontoyiannis-verdu2014,
  author  = {Kontoyiannis, I. and Verd{\'u}, S.},
  title   = {Optimal Exponent for the AEP},
  journal = {IEEE Transactions on Information Theory},
  volume  = {60},
  number  = {11},
  pages   = {6753--6759},
  year    = {2014},
}