More on Asymptotic Equipartition Property

In the above communication system, if $x sub i is similar to p(x)$ What $p(x sup n)$ governs $sup n X sub C$ ?
Since AEP states,

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

Multiplying both sides by n and taking antilog (log a = log₂ a ⇒ for log₂ a = c, a = 2^c), we get

$p(x sup n) tends to 2 index (-n times H(X))$

Let us define a special set (called typical set) ⁿA_ε ⊂ ⁿX_C such that

$sup n A sub epsilon = set of elements x sup n belonging to sup n X sub C given p(x sup n) is greaterthanequal to 2 index (-n times (H(X) + epsilon)) and p(x sup n) is lessthanequal to 2 index (-n times (H(X) - epsilon))$

where ε > 0 is an arbitrarily small constant.

Therefore, if xⁿ ∈ ⁿA_ε

$log of 2 index (-n times (H(X) + epsilon)) = -n times (H(X) + epsilon)$

Hence,

$H(X) - epsilon is lessthanequal to log of (1 over p(x sup n)) over n is lessthanequal to H(X) + epsilon$

Therefore the typical set ⁿA_ε is the set of xⁿ for which $log (1 over p(x sup n)) over n$ lies within ±ε of the entropy H(X).

❶

How typical is the typical set ⁿA_ε?

It is typical enough that, for sufficiently large n

$P (x sup n belongs to sup n A sub epsilon) is greaterthan (1 - epsilon)$

(Th.3.1.2 p.59). ❷

How big is the typical set ⁿA_ε?

The size of a typical set is given by

$(1 - epsilon) times 2 index (n times (H(X) - epsilon)) is lessthanequal to |sup n A sub epsilon| is lessthanequal to 2 index (n times (H(X) + epsilon))$

where |ⁿA_ε| is the cardinality of ⁿA_ε.

Note that if H(X) < log₂|X| where log₂|X| is the maximum possible entropy, then ⁿA_ε will frequently be a small fraction of ⁿX_C which accounts for most of the ⁿX_C that are emitted. ❸