The Exercise

A source emits letters $x_1, x_2, \dots$ from a finite alphabet $\mathcal{X}$, independently, each equal to the letter $a$ with probability $p(a)$, so that a block $x = (x_1, \dots, x_n)$ of $n$ letters has probability $p(x_1) \cdots p(x_n)$. Each block is to be written as a string of bits without error: two different blocks never receive the same string, though the strings may differ in length. The code numbers the typical blocks apart from the others and spends one bit to say which list a block is in. The exercise is to show that for any rate $R$ above the entropy of the source in bits per letter, the tolerance that defines typicality can be chosen, and the blocks taken long enough, so that the expected length of the string is at most $nR$ bits.

The Entropy and the Code

The Shannon entropy of a distribution $p$ on a finite alphabet $\mathcal{X}$ is the real number $$H(p) = -\sum_{a \in \mathcal{X}} p(a) \log p(a),$$(1)^✦ with the natural logarithm, so that $H(p)$ is measured in nats and $H(p)/\log 2$ is the entropy in bits.

Fix a block length $n$ and a tolerance $\varepsilon$, and let $T(n,\varepsilon)$ be the set of blocks $x$ of length $n$ with $-\frac{1}{n}\log\big(p(x_1)\cdots p(x_n)\big)$ within $\varepsilon$ of $H(p)$, the blocks typical with tolerance $\varepsilon$.

The typical sequence code $C_{n,\varepsilon}$ sends a block $x \in \mathcal{X}^n$ to the string of bits $$C_{n,\varepsilon}(x) = \begin{cases} 0\, b_T(x), & x \in T(n,\varepsilon),\\ 1\, b(x), & x \notin T(n,\varepsilon), \end{cases}$$(2)^✦ where $b_T(x)$ is a string of fixed length $\ell_T$ that numbers $x$ among the typical blocks, with $|T(n,\varepsilon)| \le 2^{\ell_T}$, and $b(x)$ is a string of fixed length $\ell$ that numbers $x$ among all blocks, with $|\mathcal{X}|^n \le 2^{\ell}$. The length of the codeword, $1 + \ell_T$ bits for a typical block and $1 + \ell$ bits for any other, is written $|C_{n,\varepsilon}(x)|$.

The Claim

What Is Checked

The claim is stated over the Shannon entropy (1), against which the rate is measured, and over the code $C_{n,\varepsilon}$ of (2).