Let $X$ and $Y$ be stochastic variables on respectively $n$ and $m$ points with $m>n$ and a joint probability distribution $p(x,y)$. The mutual information is $$ I(X ;Y) = H(X) + H(Y) - H(X,Y) $$ where $H(X)$ denotes the Shannon entropy of the marginal of $p$ over $X$ and $H(X,Y)$ is the Shannon entropy of the joint distribution $p$.

Is it possible to compress $Y$ to the size of $X$ whilst preserving mutual information? That is, does there exist a stochastic matrix $T: \mathbb{R}^m \rightarrow \mathbb{R}^n$ which sends $p$ to $(I_n\otimes T)p$, such that $$ I(X;Y) = I(X;Y^\prime) $$

Intuitively this makes sense as the maximal amount of information that they can share should depend on the smallest dimension of the two. I however couldn't find any result like this.


2 Answers 2


Ahlswede and Gacs showed the following 'strong data processing inequality' in the mid-70s.

Suppose the channel $P_{U|V}$ is such that $0$ error communication is not possible over it - i.e., for every $v \neq v', \exists u: P(u|v)P(u|v')> 0$. Then there exists an $\eta < 1$ such that for any Markov chain $W-V-U,$ $$I(W;U) \le \eta I(V;U).$$

In our case, let $W$ be the quantised version of $Y$, $V=Y$ and $U= X$. If the channel $P_{X|Y}$ cannot have $0$ error communication, then it follows that we must lose some information in the quantisation. So, basically anything can serve as a counterexample (although it's non-trivial to see how).

Strictly speaking the inequality above is quite a big hammer - for instance, it shows that varying the distribution of $Y$ while keeping the channel $P_{X|Y}$ fixed cannot help.

See this recent survey due to Polyanskiy and Wu for an account of strong data processing inequalities. The inequality I cite is equation (21) there.

An alternate:

In a comment you had asked how few levels $Y$ needed to be quantised to in order to attain good compression of the information about $X$. This paper studies a slightly different problem, which you may be interested in. In short: consider the set of random variables $X,Y$ with joint distribution such that $I(X;Y) \ge \beta$. They study the minimax question of how much information a $M<|\mathcal{Y}|$ level quantiser can retain about $X$ in the worst case as one varies $P_{XY}$ subject to the prior constraint. In fact, with their converse results, you can find other counterexamples for your problem - for instance, they show that for binary $X$, there exists some joint distribution $P_{XY}$ such that any binary quantisation $Y_2$ of $Y$ must have $I(X;Y_2) \le 3\beta/\max( \log(1/\beta), 1). $ This means that there should exist distributions with mutual information $< 1/8$ for which you cannot retain sufficent mutual information in any $2$-level quantisation (possibly you can figure something out explicitly using the constructions in their upper bound).


Here's my attempt at answering this interesting question.

The random variables $X,Y,T(Y)$ form a Markov chain $X\rightarrow Y \rightarrow T(Y)$. By the data processing inequality, it always holds $$ I(X;T(Y))\leq I(X;Y) $$ with equality if and only if it also holds $X\rightarrow T(Y) \rightarrow Y$.

The latter condition is what defines the so called sufficient statistic in estimation theory [Cover&Thomas, Ch. 2]. Therefore, your question may be equivalently posed as follows: Is it always possible to find a sufficient statistic $T(Y)$ of dimension smaller than the dimension of the "parameter" $X$?

It turns out that this is not always possible. Consider the following example (taken from these slides). $X\in \mathbb{R}$ is an one-dimensional random variable (of some arbitrary distribution) and $Y\in \mathbb{R}^n$ is an $m$-dimensional random variable whose elements are i.i.d. uniformly distributed over the interval $[X,X+1]$. It can be shown that the so-called minimal sufficient statistic in this case is the two-dimensional vector $(\min\{Y_i\},\max\{Y_i\})$. Therefore, although "compression" of the observation is possible, the dimension of the minimal sufficient statistic is greater than that of $X$. Since the transform $T$ is non-linear in this case, it follows that restricting our attention to linear transforms can only result in an increase of the sufficient statistics dimension.

  • 3
    $\begingroup$ Interesting. How do you get $X\rightarrow Y$? Why not $Y\rightarrow X$? And if I'm not mistaken, the example you give is in a continuous probability distribution. Is it possible to give a counter-example in the form of a concrete joint-probability distribution of some finite discrete variables? Furthermore, if the statement in the question is not true. Is it possible to give some bounds on the maximal size of an optimal compression? $\endgroup$
    – John
    Apr 21, 2017 at 11:19
  • 2
    $\begingroup$ @John From my understanding, you are considering the case where $p(y'|y,x)=p(y'|y)$, i.e., $Y'$ is conditionally independent of $X$ given $Y$. This is the case, for example, when $Y'$ is a (possibly deterministic) transformation of $Y$ that is independent of the value of $X$. From the standard chain rule, it follows that $p(x,y,y')=p(x)p(y|x)p(y'|y,x)=p(x)p(y|x)p(y'|y)$, which corresponds to the Markov chain $X \rightarrow Y \rightarrow Y'$. I am afraid I do not have answers for your other interesting questions. $\endgroup$
    – Stelios
    Apr 21, 2017 at 11:39
  • $\begingroup$ @Stelios link to the slides is dead, do you happen to have an alternate link? $\endgroup$ Nov 9, 2019 at 1:50
  • $\begingroup$ @stochasticboy321 Unfortunately, I have not. However, I did find now another reference which has an example (with only a hint of proof) where the sufficient statistics dimension is greater than the variable to be estimated. Check example 12 in these notes. $\endgroup$
    – Stelios
    Nov 9, 2019 at 5:28
  • $\begingroup$ I will, thanks! $\endgroup$ Nov 9, 2019 at 5:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .