More on Asymptotic Equipartition Property

In the above communication system, if What governs ?
Since AEP states, Multiplying both sides by n and taking antilog (log a = log2 a ⇒ for log2 a = c, a = 2c), we get Let us define a special set (called typical set) nAεnXC such that where ε > 0 is an arbitrarily small constant.

Therefore, if xnnAε

Hence, Therefore the typical set nAε is the set of xn for which lies within ±ε of the entropy H(X).

How typical is the typical set nAε?

It is typical enough that, for sufficiently large n

(Th.3.1.2 p.59).

How big is the typical set nAε?

The size of a typical set is given by

where |nAε| is the cardinality of nAε.

Note that if H(X) < log2|X| where log2|X| is the maximum possible entropy, then nAε will frequently be a small fraction of nXC which accounts for most of the nXC that are emitted.

What is the number of data–bits required to form a typical set nAε?

If,

Then Note that Also Therefore and ln is the number of .

Therefore, if xi are equally probably

Then and hence data compression is not possible. For data compression to be possible, it needs to be

Next:

Summary (p:3) ➽