I have a setting in which there are two random variables $x_1, x_2$, which takes values in a set of size $m$. They are uniformly and independently distributed. There is also a random variable $(i,y)$ with the property that $x_i = y$, but it is otherwise completely arbitrary. I'd like to understand the mutual information $I(\; (i,y)\; : \; x_1,x_2 \;)$.

My guess is that this information is at least $\log(m) = H(x_1) = H(x_2)$. (logs are base 2 here.) My intuition for this is that $(i,y)$ determines one of the values $x_1$ or $x_2$ (depending on $i$), and so the entropy from that determination goes into the mutual information. However, the best way I can see to realize this intuition is to argue that

$$I(\; (i,y) \;:\; x_1,x_2 \;) \ge I(\; (i,y) \;:\; x_1,x_2 \;\mid\; i \;)$$

via the chain rule, and try to show that, for fixed choices of $i$, the mutual information is at least $\log(m)$ conditioned on $i$.

Unfortunately, this is doomed to fail, as evidenced by the setting where we view $x_1$ and $x_2$ as independent coin flips ($m=2$), and $(i,y)$ has $i=0$ if $x_1=x_2$, and $y=\texttt{Heads}$ otherwise (which determines the value of $i$). The event that $i = 0$ has probability $3/4$, and, conditioned on it, $y = \texttt{Heads}$ with probability $2/3$. The event that $i=1$ has probability $1/4$, and, conditioned on it, $y = \texttt{Heads}$ with probability $1$. Thus the entropy

$$H((i,y)\mid i) = H(y\mid i) = \frac{3}{4}H_2(2/3) + \frac{1}{4}H_2(1) < 1$$

where $H_2$ is the binary entropy function. This entropy is an upper bound on the mutual information $I(\; (i,y) \;:\; x_1,x_2 \;\mid\; i \;)$, so it can't be at least $\log(m) = 1$. However, the mutual information that I'm actually interested in is 3/2.

My next best guess is that, among all distributions for $(i,y)$, some concavity property of mutual information should imply that the quantity I'm interested in is minimized when $i$ is independent of $x_1,x_2$, at which point my averaging argument does work. Unfortunately, I'm not well-versed enough to put this argument together or even decide intuitively whether it works. Any help unraveling this would be much appreciated.


I think I have a solution (detailed below), but I would appreciate it if there were a nicer, simpler solution, particularly for Part I.

The general roadmap is as in the question. We'll use a convexity property of mutual information to reduce to the case in which the variable $i$ is independent of $x_1,x_2$. We can then solve this special case using the first strategy from the question.

Part I, reducing to $i$ independent of $x_1,x_2$.

Recall that the quantity $I(u:v)$ is a function of the probabilities $P[u=u_0]$ and $P[v=v_0|u=u_0]$ where $u_0,v_0$ range over the support of $u$ and $v$. When the kind of the form $P[u=u_0]$ are fixed, and the remainder are allowed to vary, it's known that $I(u:v)$ is convex. This is the key property that we'll exploit.

For each fixed assignment $x_1,x_2 \gets \hat{x}_1,\hat{x}_2$, we are given a distribution $\mu_{\hat{x}_1,\hat{x}_2}$ over $(i,y)$ with the property that $x_i = y$ always; the goal is to construct a new distribution $\nu_{\hat{x}_1,\hat{x}_2}$ over the choices of $(i,y)$ so that

  • we still have $x_i = y$ always

  • the distribution of $i$ under $\nu_{\hat{x}_1,\hat{x}_2}$ is independent of the choice of $x_1,x_2$

  • the mutual information satisfies $$I_{\nu}(\; (i,y) \;:\; x_1,x_2 \;) \le I_{\mu}(\; (i,y) \;:\; x_1,x_2 \;)$$ where $\nu$ denotes sampling $x_0,x_1 \sim \mu$ and then sampling $(i,y)$ from $\nu_{\hat{x}_1,\hat{x}_2}$.

We'll do this by just defining $\nu_{\hat{x}_1,\hat{x}_2}$ to be the distribution that picks $\hat{x}_1',\hat{x}_2'$ uniformly at random, samples $i \sim \mu_{\hat{x}_1',\hat{x}_2'}$, and sets $y \gets \hat{x}_i$.

The distribution $\nu$ clearly has $x_i = y$ everywhere. Also, $i$ is clearly independent of $x_1,x_2$. So we just need to show the mutual information inequality.

To do this, suppose we fix a bijection $f_1$ from the support of $x_1$ to itself, and a bijection $f_2$ similarly wrt $x_2$. Let $\mu^{f_1,f_2}$ be the distribution over $x_1,x_2,i,y$ obtained by sampling $x_1,x_2 \sim \mu$, then sampling $i \sim \mu_{f_1(x_1),f_2(x_2)}$, and setting $y \gets x_i$. It follows that

  • For every $i_0$ in the support of $i$ and $y_0$ in the support of $y$, we have $$\begin{align*} \mathrm{Pr}_{\mu^{f_1,f_2}}[ i=i_0, y=y_0 ] &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0,y=y_0] \right] \\ &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0] \cdot \mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[y=y_0 \mid i=i_0] \right] \\ &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0] \; ; \; x_{i_0} = y_0 \right] \end{align*}$$ and also $$\begin{align*} \mathrm{Pr}_{\mu}[ i=i_0, y=y_0 ] &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0,y=y_0] \right] \\ &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0] \cdot \mathrm{Pr}_{\mu\mid_{x_1,x_2}}[y=y_0 \mid i=i_0] \right] \\ &= \mathbb{E}_{x_1,x_2\sim\mu}\left[ \mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0] \; ; \; x_{i_0} = y_0 \right] \end{align*}$$ whence it follows that $$\mathrm{Pr}_\mu\left[ i=i_0, y=y_0 \right] = \mathrm{Pr}_{\mu^{f_1,f_2}}\left[ i=i_0, y=f_{i_0}^{-1}(y_0) \right] $$ and hence $$H_{\mu^{f_1,f_2}}(\; i,y \;) = H_{\mu}(\; i,y \;)$$

  • and similarly for the conditional entropies $$\begin{align*} H_{\mu^{f_1,f_2}}(\; i,y \;\mid\; x_1,x_2 \;) &= H_{\mu^{f_1,f_2}}(\; i \;\mid\; x_1,x_2 \;) \\ &= \mathbb{E}_{x_1,x_2\sim\mu} H_{\mu\mid_{f_1(x_1),f_2(x_2)}}( i,y ) \\ &= \mathbb{E}_{x_1,x_2\sim\mu} H_{\mu\mid_{x_1,x_2}}( i,y ) \\ &= H_{\mu}(\; i \;\mid\; x_1,x_2 \;) \\ &= H_{\mu}(\; i,y \;\mid\; x_1,x_2 \;) \end{align*}$$ where the middle equality follows because the conditional entropy is an equally-weighted average over all the choices of $\hat{x}_1,\hat{x}_2$ in the support of $x_1,x_2$, and the effect of $f_1,f_2$ is just to shuffle the averaged quantities around.

Putting these two together, it follows that $$I_{\mu}(\; i,y \;:\; x_1,x_2 \;) = I_{\mu^{f_1,f_2}}(\; i,y \;:\; x_1,x_2 \;)$$

Note that we can view sampling $i,y$ from $\nu_{\hat{x}_1,\hat{x}_2}$ as choosing $f_1,f_2$ uniformly and independently at random, and then sampling $i,y \sim \mu^{f_1,f_2}\mid_{\hat{x}_1,\hat{x}_2}$. So in that sense, the ensemble of conditioned distributions $\{\nu_{\hat{x}_1,\hat{x}_2}\}$ for $i$ is a convex combination, over choices of $f_1,f_2$, of the ensembles of conditioned distributions $\{\mu^{f_1,f_2}\mid_{\hat{x}_1,\hat{x}_2}\}$.

Hence, by the convexity property of mutual information, we can finally say that

$$I_\mu(\; i,y \;:\; x_1,x_2 \;) \ge I_\nu(\; i,y \;:\; x_1,x_2 \;)$$

Part II, assuming $i$ is independent of $x_1,x_2$, prove the claim.

This part is much easier. We can write

$$\begin{align*} I(\; i,y \;:\; x_1,x_2 \;) &= I(\; y \;:\; x_1,x_2 \;|\; i \;) + I(\; i \;:\; x_1,x_2 \;) \\ &= I(\; y \;:\; x_1,x_2 \;|\; i \;) \\ &= H( y | i ) - H( y | i,x_1,x_2 ) \\ &= H( y | i ) \end{align*}$$

Then, conditioning on $i=i_0$, we know $y = x_{i_0}$, and $x_{i_0}$ is independent of $i$, so $H(y | i=i_0) = H(x_{i_0}) = \log(m)$, and we're done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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