Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 323 / 2 / i / b

Table of contents
- Solution b

Solution

Every member of the typical set has probability at least

2^{- n (H (X) + ε)}

. Summing these probabilities gives

1 \geq \sum_{x^{n} \in T_{ε}^{(n)}} p (x^{n}) \geq ∣ T_{ε}^{(n)} ∣ 2^{- n (H (X) + ε)},

so

∣ T_{ε}^{(n)} ∣ \leq 2^{n (H (X) + ε)} .

The upper bound itself holds at every block length. For sufficiently large

n

, the high-probability property also gives the companion lower bound

1 - δ \leq P (T_{ε}^{(n)}) \leq ∣ T_{ε}^{(n)} ∣ 2^{- n (H (X) - ε)},

hence

∣ T_{ε}^{(n)} ∣ \geq (1 - δ) 2^{n (H (X) - ε)}

. Together these are the typical-set cardinality bounds underlying Shannon source coding theorem.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version