Can information be extracted more precisely using more random trials?

Question

Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?

Answer 1

The characterization is given in terms of a so-called auxiliary random variable. It is as explicit of an answer as you'll get, unless you consider very special cases (like jointly Gaussian $X,Y$, or binary-valued $X,Y$). Namely, you have

$$ \lim_{n\to\infty}\min_{f: x^n \mapsto f(x^n)\in \{1,\dots,2^{nR}\}} \frac{1}{n}H(Y^n|f(X^n)) = \inf_{U : Y-X-U, I(X;U)\leq R} H(Y|U). $$

In the expression on the right, we look over all random variables $U$, jointly distributed with $X,Y$, such that $Y$ and $U$ are conditionally independent given $X$, and $I(X;U)\leq R$, where $I$ denotes the usual mutual information.

This is a special case of the indirect source coding problem (or, more generally CEO problem) under logarithmic loss. The information bottleneck problem corresponds to the unconstrained optimization problem associated to that on the right (i.e., the IB functional is equivalent to the Lagrangian of the thing on the right).

Here is a quick sketch of the proof.

Claim (Lower Bound): For any $f: x^n \mapsto f(x^n) \in \{1,\dots, 2^{nR}\}$, there is a random variable $U$ satisfying $Y-X-U$, $I(X;U)\leq R$ and $\frac{1}{n}H(Y^n|f(X^n)) \geq H(Y|U)$.

Proof: By the chain rule, write $$ \frac{1}{n}H(Y^n|f(X^n)) = \frac{1}{n}\sum_{i=1}^n H(Y_i|Y^{i-1},f(X^n))= \frac{1}{n}\sum_{i=1}^n H(Y_i|V_i), $$ where we define $V_i := (Y^{i-1},f(X^n))$. Observe that, since $(X^n,Y^n)$ are iid draws of $(X,Y)$, we have $Y_i - X_i - V_i$ for each $i=1,\dots, n$. Now, on a common probability space with $(X,Y)$ construct a random variable $U$ as follows. Given $X=x$, draw $Q$ uniformly from $\{1,\dots, n\}$, and take $U = (V_Q,Q)$, where $V_Q|\{Q=i, X=x\} \sim p_{V_i|X_i}(\cdot | x)$. Evidently, we have $Y - X - U$, and by definition of $U$, $$ \frac{1}{n}H(Y^n|f(X^n)) = \frac{1}{n}\sum_{i=1}^n H(Y_i|V_i) = H(Y|U), $$ since the $Y_i$'s are iid. Now, for each $i=1,\dots, n$, we have $X_i - (X^{i-1},f(X^n)) - (Y^{i-1},f(X^n))$ (again, using the fact that $(X^n,Y^n)$ are iid draws of $X,Y$ together with the fact that $f$ is a function of the $x_i$'s), so properties of entropy and the data processing inequality give $$ R \geq \frac{1}{n}I(X^n ; f(X^n)) = \frac{1}{n}\sum_{i=1}^n I(X_i ; X^{i-1},f(X^n)) \geq \frac{1}{n}\sum_{i=1}^n I(X_i ; V_i) = I(X;U). $$

Claim (Upper Bound): If $Y-X-U$ satisfy $I(X;U)\leq R$, then for $n$ sufficiently large, there is a function $f: x^n \to f(x^n) \in \{1,\dots, 2^{nR}\}$ with $\frac{1}{n}(H(Y^n| f(X^n))+o(n)) = H(Y|U)$

Proof: Fix any random variable $U$ on a common probability space with $(X,Y)$ such that $Y-X-U$ and $I(X;U) < R$. Generate $2^{nR}$ sequences $U^n(1), \dots, U^n(2^{nR})$ independently, according to $p_U^{\otimes n}$. By standard typicality arguments, if we observe $X^n$, then with high probability there is an index $f(X^n)\in \{1,\dots, 2^{nR}\}$ such that $U^n(f(X^n))$ is jointly typical with $X^n$ (and therefore also $Y^n$ by the Markov Lemma). By standard properties of (conditional) typical sets, we have $$ \frac{1}{n}H(Y^n| f(X^n)) \sim H(Y|U). $$