Rate Distortion Theory

Assume WLOG $p < \tfrac12$. Let $\oplus$ denote mod-2 addition, so $X \oplus \hat X = 1$ is equivalent to $X \ne \hat X$.

Step 1: Lower bound. For any joint distribution satisfying the constraint,

$I(X;\hat X) = H(X) - H(X\mid \hat X) = H(p) - H(X \oplus \hat X \mid \hat X)$

The rewriting is the key move: given $\hat X$, knowing $X$ is the same as knowing the error pattern $X \oplus \hat X$, so the conditional entropy can be expressed in terms of errors rather than symbols. Then

$\ge H(p) - H(X\oplus \hat X) \ge H(p) - H(D)$

using conditioning-reduces-entropy, then $\Pr(X\ne\hat X)\le D$ together with the fact that $H(D)$ increases with $D$ for $D \le \tfrac12$. Hence $R(D) \ge H(p) - H(D)$.

Step 2: Achieve it with a test channel. Choose $(X,\hat X)$ jointly distributed as a binary symmetric channel with crossover $D$ running from $\hat X$ to $X$ — note the direction: $\hat X$ is the input, $X$ the output. Choose the distribution of $\hat X$ so that the output distribution of $X$ is the specified one. With $r = \Pr(\hat X = 1)$, solve

$r(1-D) + (1-r)D = p \quad\Longrightarrow\quad r = \frac{p - D}{1 - 2D}$

If $D \le p \le \tfrac12$ then $r \in [0,1]$ is a valid probability. For this joint distribution $I(X;\hat X) = H(p) - H(D)$ and the expected distortion is exactly $\Pr(X \ne \hat X) = D$.

Step 3: The degenerate range. If $D \ge p$, set $\hat X = 0$ with probability 1: then $I(X;\hat X) = 0$ and $D = p$, so $R(D) = 0$. Similarly if $D \ge 1-p$, set $\hat X = 1$.

∎

Step 1: Lower bound. Since $\mathbb{E}(X-\hat X)^2 \le D$,

$I(X;\hat X) = h(X) - h(X\mid\hat X) = \frac{1}{2}\log(2\pi e)\sigma^2 - h(X - \hat X \mid \hat X)$

using translation invariance of differential entropy (given $\hat X$, subtracting it is a shift). Then

$\ge \frac{1}{2}\log(2\pi e)\sigma^2 - h(X - \hat X) \ge \frac{1}{2}\log(2\pi e)\sigma^2 - h\big(\mathcal{N}(0, \mathbb{E}(X-\hat X)^2)\big)$

by conditioning-reduces-entropy and then the Gaussian max-entropy theorem. Evaluating and using $\mathbb{E}(X-\hat X)^2 \le D$:

$= \frac{1}{2}\log(2\pi e)\sigma^2 - \frac{1}{2}\log(2\pi e)\mathbb{E}(X-\hat X)^2 \ge \frac{1}{2}\log(2\pi e)\sigma^2 - \frac{1}{2}\log(2\pi e)D = \frac{1}{2}\log\frac{\sigma^2}{D}$

Step 2: The test channel. It is more convenient to specify $f(x\mid\hat x)$ — sometimes called the test channel, emphasizing the duality with channel capacity. For $D \le \sigma^2$ choose

$X = \hat X + Z, \qquad \hat X \sim \mathcal{N}(0, \sigma^2 - D), \quad Z \sim \mathcal{N}(0,D)$

with $\hat X$ and $Z$ independent. This gives $I(X;\hat X) = \tfrac12\log\frac{\sigma^2}{D}$ and $\mathbb{E}(X-\hat X)^2 = D$, meeting the bound. If $D > \sigma^2$, take $\hat X = 0$ with probability 1.

∎

Non-increasing: $R(D)$ is a minimum of mutual information over increasingly larger sets as $D$ grows — a looser constraint cannot raise a minimum.

Convex: take two pairs $(R_1,D_1)$, $(R_2,D_2)$ on the curve, achieved by joints $p_1(x,\hat x) = p(x)p_1(\hat x\mid x)$ and $p_2$. Consider $p_\lambda = \lambda p_1 + (1-\lambda)p_2$. Distortion is a linear function of the distribution, so $D(p_\lambda) = \lambda D_1 + (1-\lambda)D_2$. Mutual information, on the other hand, is a convex function of the conditional distribution, so

$R(D_\lambda) \le I_{p_\lambda}(X;\hat X) \le \lambda I_{p_1}(X;\hat X) + (1-\lambda)I_{p_2}(X;\hat X) = \lambda R(D_1) + (1-\lambda)R(D_2)$

∎

We show that any $(2^{nR},n)$ code with distortion $\le D$ has $R \ge R(D)$ — and in fact this holds even for randomized mappings $f_n, g_n$, as long as $f_n$ takes at most $2^{nR}$ values. Let $\hat X^n = g_n(f_n(X^n))$.

$nR \overset{(a)}{\ge} H(f_n(X^n)) \overset{(b)}{\ge} H(f_n(X^n)) - H(f_n(X^n)\mid X^n) = I(X^n; f_n(X^n))$

$\overset{(c)}{\ge} I(X^n;\hat X^n) = H(X^n) - H(X^n\mid\hat X^n) \overset{(d)}{=} \sum_{i=1}^n H(X_i) - H(X^n\mid\hat X^n)$

$\overset{(e)}{=} \sum_i H(X_i) - \sum_i H(X_i \mid \hat X^n, X_{i-1},\ldots,X_1) \overset{(f)}{\ge} \sum_i H(X_i) - \sum_i H(X_i\mid\hat X_i) = \sum_i I(X_i;\hat X_i)$

$\overset{(g)}{\ge} \sum_i R\big(\mathbb{E}d(X_i,\hat X_i)\big) = n\sum_i \frac{1}{n}R\big(\mathbb{E}d(X_i,\hat X_i)\big) \overset{(h)}{\ge} nR\left(\frac{1}{n}\sum_i \mathbb{E}d(X_i,\hat X_i)\right)$

$\overset{(i)}{=} nR\big(\mathbb{E}d(X^n,\hat X^n)\big) \overset{(j)}{\ge} nR(D)$

Justifications:

• (a) the range of $f_n$ has at most $2^{nR}$ values
• (b) $H(f_n(X^n)\mid X^n)\ge 0$
• (c) the data processing inequality
• (d) the $X_i$ are independent
• (e) chain rule for entropy
• (f) conditioning reduces entropy
• (g) definition of the rate distortion function
• (h) convexity of $R(D)$ plus Jensen’s inequality — this is why the lemma was needed
• (i) definition of distortion for blocks of length $n$
• (j) $R(D)$ non-increasing, and $\mathbb{E}d(X^n,\hat X^n)\le D$

∎

All four conditions are normalized sums of i.i.d. random variables — including $d(X^n,\hat X^n) = \frac1n\sum_i d(X_i,\hat X_i)$ — so each tends to its expected value with probability 1, and the set satisfying all four has probability tending to 1.

∎

$p(\hat x^n\mid x^n) = p(\hat x^n)\frac{p(x^n,\hat x^n)}{p(x^n)p(\hat x^n)} \le p(\hat x^n)\frac{2^{-n(H(X,\hat X)-\epsilon)}}{2^{-n(H(X)+\epsilon)}2^{-n(H(\hat X)+\epsilon)}} = p(\hat x^n)2^{n(I(X;\hat X)+3\epsilon)}$

∎

Let $f(y) = e^{-y} - 1 + y$; then $f(0)=0$ and $f'(y) = 1 - e^{-y} > 0$ for $y>0$, so $f(y)>0$, giving $1-y \le e^{-y}$ and hence $(1-y)^n \le e^{-yn}$ — the case $x=1$. The case $x=0$ is immediate. For $0\le x\le 1$, $g_y(x) = (1-xy)^n$ is convex in $x$, so

$g_y(x) \le (1-x)g_y(0) + xg_y(1) = (1-x) + x(1-y)^n \le 1 - x + xe^{-yn} \le 1 - x + e^{-yn}$

∎

Fix $p(\hat x\mid x)$ achieving the minimum, so $I(X;\hat X) = R(D)$, and compute $p(\hat x) = \sum_x p(x)p(\hat x\mid x)$.

Codebook. Randomly generate $2^{nR}$ sequences $\hat X^n$ i.i.d. $\sim \prod_i p(\hat x_i)$, indexed $w \in \{1,\ldots,2^{nR}\}$, revealed to encoder and decoder.

Encoding. Encode $X^n$ by $w$ if $(X^n,\hat X^n(w)) \in A_{d,\epsilon}^{(n)}$; if several, send the least; if none, send $w=1$.

Decoding. Reproduce $\hat X^n(w)$.

Step 1: Split the distortion by whether a good codeword exists. For a fixed codebook, sequences fall into two classes:

• Those with a distortion-typical codeword: distortion $< D + \epsilon$, and total probability at most 1, so they contribute at most $D+\epsilon$.
• Those without: let $P_e$ be their total probability; each contributes at most $d_{\max}$, so they contribute at most $P_e d_{\max}$ — this is where boundedness of the distortion measure is used.

$\mathbb{E}d(X^n,\hat X^n(X^n)) \le D + \epsilon + P_e d_{\max}$

So everything reduces to showing $P_e$ is small.

Step 2: Set up $P_e$ and swap the order of summation. Let $J(\mathcal{C})$ be the set of $x^n$ for which at least one codeword is distortion typical. Then

$P_e = \sum_{\mathcal{C}} P(\mathcal{C})\sum_{x^n \notin J(\mathcal{C})} p(x^n) = \sum_{x^n} p(x^n) \sum_{\mathcal{C}: x^n\notin J(\mathcal{C})} p(\mathcal{C})$

Reading it the second way: the probability of choosing a codebook that fails to represent $x^n$, averaged over $x^n$.

Step 3: One codeword’s failure probability. Let $K(x^n,\hat x^n) = 1$ if the pair is distortion typical, else 0. A single random codeword fails to represent a fixed $x^n$ with probability $1 - \sum_{\hat x^n} p(\hat x^n)K(x^n,\hat x^n)$, so all $2^{nR}$ independent codewords fail with probability

$P_e = \sum_{x^n} p(x^n)\left[1 - \sum_{\hat x^n} p(\hat x^n)K(x^n,\hat x^n)\right]^{2^{nR}}$

Step 4: Apply Lemma 2 to convert the marginal into the conditional.

$P_e \le \sum_{x^n} p(x^n)\left[1 - 2^{-n(I(X;\hat X)+3\epsilon)}\sum_{\hat x^n}p(\hat x^n\mid x^n)K(x^n,\hat x^n)\right]^{2^{nR}}$

Step 5: Apply Lemma 3 with $x = \sum_{\hat x^n}p(\hat x^n\mid x^n)K$ and $y = 2^{-n(I+3\epsilon)}$, $n \to 2^{nR}$:

$P_e \le 1 - \sum_{x^n}\sum_{\hat x^n}p(x^n)p(\hat x^n\mid x^n)K(x^n,\hat x^n) + e^{-2^{-n(I(X;\hat X)+3\epsilon)}2^{nR}}$

Step 6: Both pieces vanish. The last term equals $e^{-2^{n(R - I(X;\hat X) - 3\epsilon)}}$, which goes to zero doubly exponentially fast if $R > I(X;\hat X)+3\epsilon$ — so choosing $p(\hat x\mid x)$ to achieve the minimum, $R > R(D)$ suffices. The first two terms are $\Pr\big((X^n,\hat X^n)\notin A_{d,\epsilon}^{(n)}\big) < \epsilon$ by Lemma 1.

Step 7: Extract one good code. For any $\delta > 0$ there exist $\epsilon$ and $n$ such that the expected distortion averaged over random codebooks is below $D+\delta$; hence at least one codebook $\mathcal{C}^*$ achieves it. Since $\delta$ was arbitrary, $(R,D)$ is achievable whenever $R > R(D)$.

∎

Codebook, encoding and decoding as before but with $A_\epsilon^{*(n)}$. Source sequences now fall into three classes:

• Non-typical $x^n \notin A_\epsilon^{*(n)}$: total probability $<\epsilon$ for large $n$, contributing at most $\epsilon d_{\max}$.
• Typical, with a jointly typical codeword: strong joint typicality plus continuity of the distortion in the joint distribution ensures they are also distortion typical, so distortion $\le D + \epsilon d_{\max}$.
• Typical, with no jointly typical codeword: probability $P_e$, contributing at most $P_e d_{\max}$.

Expanding as before and substituting the lower bound from the lemma, with $(1-x)^n \le e^{-nx}$:

$P_e \le e^{-\left(2^{nR}2^{-n(I(X;\hat X)+\epsilon_1)}\right)}$

which $\to 0$ if $R > I(X;\hat X)+\epsilon_1$. So not only is the expected distortion close to $D$ — with probability going to 1 we find a codeword whose distortion is less than $D+\delta$.

∎