Mutual information between x1,x2 and i,xi where i is random

Question

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.

Answer 1

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.