Asymptotic Equipartition Property

The asymptotic equiparitition property (AEP) is central in information theory and is the consequence of the law of large numbers.

Types of Convergence

A random variable is: a mapping from its set of sample values \(\Omega\) onto \(\cal R\).

$$X : \Omega \to \cal R$$ $$~~~~~ \xi \to X(\xi)$$

In the cases we have been discussing, \(\Omega = \cal X\) and we map onto \([0,1]\).

Sure Convergence

A random sequence \(X_1, . . .\) converges surely to r.v. \(X\) if \(\forall \xi \in \Omega\) the sequence \(X_n(\xi)\) converges to \(X(\xi)\) as \(n \to \infty\).

Almost Sure convergence

Also called convergence with probability 1, the random sequence converges a.s. (w.p. 1) to \(X\) if the sequence \(X_1(\xi), . . .\) converges to \(X(\xi)\) for all \(\xi\) except possibly on a set of \(\Omega\) of probability 0.

Convergence in Probability

The sequence converges in probability to \(X\) if \(\forall \epsilon > 0, \lim_{n \to \infty} P_r (|X_n - X| > \epsilon) \to 0\).

Convergence in Distribution

The sequence converges in distribution if the cumulative distribution function \(F_n(x) = P_r(X_n \le x)\) satisfies \(\lim_{n \to \infty} F_n(x) \to F_X(x)\) at all \(x\) for which \(F\) is continuous.

Venn diagram of relations among types of convergence:

Weak Law of Large Numbers

\(X_1, X_2, . . .\) are i.i.d, finite mean \(\mu\) and variance \(\sigma^2\), then \(A_X^n \to \mu\) in probability, where \(A_X^n = {X_1 + ... + X_n \over n}\)

$$Pr(|A_X^n − \mu| \ge \epsilon) \le {\sigma^2 \over {n\epsilon^2}}$$

Strong Law of Large Numbers

If \(X_i\) are i.i.d, and \(E_X (|X|) < \infty\), then

$$P_r(\lim_{n \to \infty} A_X^n = \mu) = 1$$

The difference between Strong and Weak lies in the limiting behavior of an infinite sequence of rv’s, but this difference is not relevant here.

Strong versus Weak Typicality Intuition

\(\cal X = \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\}\) with pmf \(p_X = (0.5, 0.25, 0.125, 0.125) \Rightarrow H(x) = H(0.5,0.25,0.125,0.125) = 1.75\) bit.
E.g. Sample sequence consisting of eight i.i.d samples:

• Strongly typical: all sequence with correct proportions
  \(\clubsuit\clubsuit\clubsuit\clubsuit\diamondsuit\diamondsuit\heartsuit\spadesuit \Rightarrow -\log p(x) = 14 = 8H(x)\).

• Not typical at all: \(-\log p(x) \neq nH(x)\)
  \(\spadesuit\spadesuit\spadesuit\spadesuit\spadesuit\spadesuit\spadesuit\spadesuit \Rightarrow -\log p(x) = 24 \neq 8H(x)\).

• Weekly typical: \(-\log p(x) = nH(x)\)
  \(\clubsuit\clubsuit\diamondsuit\diamondsuit\diamondsuit\diamondsuit\diamondsuit\diamondsuit \Rightarrow -\log p(x) = 14 = 8H(x)\).

Asymptotic Equipartition Propert(AEP)

APE

If \(X_1, X_2, ... , X_n {i.i.d. \atop \sim} p\), then

$$\align -{1\above n}\log p(X_1, X_2, ... , X_n) = -{1\above n}\sum_{i=1}^n\log p(X_i) \stackrel{p}{\to} -E[\log p(X)] = H(X) $$

** Typical Set**

Jointly Typical

Reference:

1. Thomas M. Cover, Joy A. Thomas. (2006). Elements of Information Theory. John Wiley & Sons.
2. Natasha Devroye. ECE 534: Elements of Information Theory. University of Illinois at Chicago. https://www.ece.uic.edu/ECE534 .

A good person! More about the author →