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$?

  • 2
    $\begingroup$ What is $H$? Any function of the data or something more specific? Also what do we know about the distribution of $(x, y)$? $\endgroup$
    – Vincent
    May 10, 2020 at 20:03
  • 3
    $\begingroup$ $H$ is (conditional) Shannon entropy. $(x,y)$ is distributed over $\mathcal{X}\times \mathcal{Y}$, both sets finite. $\endgroup$ May 10, 2020 at 20:04
  • $\begingroup$ My current thinking is to find $\min_s n^{-1}H(y^n|x^n \in s)$ over sets $s$ of $\exp(n(H(x)-R))$ sequences typical for $x^n$, taking $n\to\infty$. Then if one can design $f$ with fibers similar to the optimum $s$, the main question is solved. I would be surprised if this new min wasn't equal to the information bottleneck optimum, which would make design of $f$ straightforward. $\endgroup$ Jun 17, 2020 at 21:35
  • $\begingroup$ Is $f$ allowed to be a function of $n$ variables, or only a function of one variable applied element-wise? $\endgroup$
    – user44143
    Jun 20, 2020 at 5:47
  • $\begingroup$ $f$ is over $n$ vars jointly. The other case is already a single-letter problem whose answer can (in principle) be numerically estimated. $\endgroup$ Jun 20, 2020 at 17:51

1 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). $$

  • $\begingroup$ Tom, thanks for the proof. I think this is actually subtly different than source coding under logarithmic loss. Choosing the best encoder here is minimizing a different objective: in this case (1) the "loss function" simultaneously depends on all $n$ source letters and the encoder word in some complex way. in the source coding problem (2) the loss function is an average of $n$ identical single-letter losses. Your proof shows that the minima of the two problems are the same. $\endgroup$ Aug 30, 2021 at 17:53
  • $\begingroup$ Put another way: after conditioning on the encoding, the source letters are no longer necessarily independent. This question's objective function keeps track of this non-independence, the source coding problem does not. $\endgroup$ Aug 30, 2021 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.