 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-66/4/ii/solution

Use the weak notion of a typical set. For a word

z^{n} = (z_{1}, \dots, z_{n})

write

P_{Z}^{n} (z^{n}) = \prod_{i = 1}^{n} P_{Z} (z_{i})

T_{δ}^{n} (P_{Z}) = {z^{n} : P_{Z}^{n} (z^{n}) > 0, - \frac{1}{n} lo g_{2} P_{Z}^{n} (z^{n}) - H (Z) \leq δ} .

2^{- n (H (Z) + δ)}

and

2^{- n (H (Z) - δ)}

. Words containing zero-probability symbols are excluded. These two bounds and the weak law of large numbers provide the three conclusions below.

 New to topics? Read the docs here!