More on Asymptotic Equipartition Property

Fig 1 Symbol Register
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 = log2 a ⇒ for log2 a = c, a = 2c), we get
p(x sup n) tends to 2 index (-n times H(X))
Let us define a special set (called typical set) nAεnXC 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 xnnAε

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 nAε is the set of xn for which log (1 over p(x sup n)) over n lies within ±ε of the entropy H(X).


How typical is the typical set nAε?

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 nAε?

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 |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,

l = number of bits required
Then
l approx= log base 2 |sup n A sub epsilon| + 1 + 1
Note that
1 is added because log(*) may not be an integer while the second 1 is added to distinguish from sup n A sub epsilon and (not) sup n A sub epsilon
Also
log base 2 |sup n A sub epsilon| + 1 + 1 is lessthanequal to n times H(X) + n times epsilon + 1 + 1
Therefore
log base 2 |sup n A sub epsilon| is lessthanequal to n times H(X) + n times epsilon
and
l over n is lessthanequal to H(X) + epsilon + 2 over n
ln is the number of bits over characters (x belongs to X).

Therefore, if xi are equally probably

Fig 1 Symbol Register

Then
H(X) = log base 2 |X|
and hence data compression is not possible. For data compression to be possible, it needs to be
H(X) is lessthan log base 2 |X|


Next:

Summary (p:3) ➽