 Solution

ID: past-exam-of-the-information-theory-course-of-the-university-of-oxford/2023/2/c/i/solution

For every

x^{n} \in A^{n, ε}

, the defining typical set constraint implies

2^{- n (H (p) + ε)} \leq p_{n} (x^{n}) \leq 2^{- n (H (p) - ε)} .

Let

S_{n} = A^{n, ε} \cap B^{n, ε}

. Summing the lower probability mass bound over

S_{n}

gives

1 \geq Pr (X^{n} \in S_{n}) = \sum_{x^{n} \in S_{n}} p_{n} (x^{n}) \geq ∣ S_{n} ∣ 2^{- n (H (p) + ε)} .

Therefore

∣ A^{n, ε} \cap B^{n, ε} ∣ \leq 2^{n (H (p) + ε)} .

The sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer

n

 New to topics? Read the docs here!