Mutual information between x1,x2 and i,xi where i is random 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.
 A: 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.
