Asymptotic Equipartition Property

Assume an information source X passing symbols x_i into a symbol register xⁿ = (x₀, x₁, …, x_n-1). The output symbol can therefore be expressed as a set of compound symbol ⁿX_C. Therefore

$p(x sup n) = P (x sub 0, x sub 1, ..., x sub n-1)$

Case 1: If X is a DMS then, each x_i are statistically independent. Therefore

$log p(x sup n) = for i = 0 to n-1, sum of log p(x sub i)$

Since n = # of individual symbols in xⁿ, dividing both sides by −1 ∕ 3

$(-1 over n) times log p(x sup n) = (-1 over n) times for i = 0 to n-1, sum of log p(x sub i)$

If n → ∞

$limit as n tends to infinity of (-log p(x sup n)) over n = limit as n tends to infinity of (1 over n) times for i = 0 to n-1, sum of log (1 over p(x sub i))$

We know that, for a collection of n symbols (n trials)

$Expected value of log (1 over p(x sub i)) = n times p(x sub i)$

Thus

$sum of log (1 over p(x sub i)) is approximately equal to the expected value of log (1 over p(x sub i))$

Therefore when n → ∞

$AEP is defined as limit as n tends to infinity of (-log p(x sup n)). And AEP tends to H(X)$

❶

Case 2: If X is not a DMS, i.e., X has memory then, its Entropy Rate may be defined as

$H(X sub R) is approximately= to limit as n tends to infinity of H(x sub 0, x sub 1, ..., x sub n-1) over n$

Note that if X was a DMS

$H(X sub R) is approximately= to H(X)$

Therefore, in general

$H(X sub R) is lessthan H(X) and H(X sub R) = H(X) iff X is DMS$
Case 3: If X is an Ergodic source, then

$limit as n tends to infinity of (-log p(x sup n)) over n tends to H(X sub R)$

This is called Shannon-McMillan-Breiman Theorem (S-M-B Th.) (Cover & Thomas, 2006, p. 646-647). Note that AEP definition used $H(X)$ but S-M-B Th. uses $H(X sub R)$ .

❷

An Ergodic source

Ergodic source are source whose

Probabilities don't change with time, i.e., stationary.
For any and all of its statistics,

Time average = Ensemble average

❸

What is the practical consequence of AEP? i.e, $limit as n tends to infinity of (-log p(x sup n)) over n$

Asymptotic Equipartition Property (AEP) makes lossless data compression possible. Lossless data compression is called data compaction.

❹

Reference:

Cover, T. M., & Thomas, J. A. (2006). Lemma 16.8.1. In 2nd Edition, Elements of Information Theory (pp. 646-647). Hoboken, New Jersey: John Wiley & Sons, Inc.

✪

Next:

More on AEP (p:2) ➽

✪

Lectures on Information Theory

Section 1

Section 2

Section 3

An Ergodic source