# Prove or disprove a mutual information inequality

I have $$n$$ IID Bernoulli random variables denoted by $$X_1,X_2,\ldots X_n$$ with parameter $$p$$.

I am interested in knowing if the following inequality involving mutual information holds :

$$\boxed{\max_{p} I(X_1+X_2+...+X_n;Y)\leq \max_{p} I(2X_1+X_3+...+X_n;Y) \leq ...\leq \max_{p} I(nX_1;Y)}$$

Note that $$p$$ is variable and can be different across different mutual information terms in the inequality.

Here, $$Y$$ is a binary random variable taking values in $$\{0,1\}$$. Also, $$Y=0$$ with probability $$\frac{1}{x+5}$$ when the input, ie, the first argument in the mutual information $$I(X;Y)$$ takes a value $$x$$.

Note: In fact, I conjecture that the inequality even holds for any decreasing transition probability in the place of $$\frac{1}{x+5}$$.

Can someone help me provide some insights or ways of proving these? In fact, my numerical simulations tend to agree with the inequality. Any help is appreciated.

Numerical evidence:

I considered $$n=3$$ as example. I found the following through simulation. $$\max_{p} I(X_1+X_2+X_3;Y)=0.0027$$ and is at $$p=0.38$$.

$$\max_{p} I(2X_1+X_3;Y)=0.0043$$ and is at $$p=0.44$$.

$$\max_{p} I(3X_1;Y)=0.0075$$ and is at $$p=0.52$$.

Also, when I considered a constant value of $$p$$ across all terms in the inequality, the inequality still seems to hold for the transition probability function $$\frac{1}{x+5}$$. But, it did not hold for other decreasing transition probability functions that I tried.

The original inequality with $$\max_p$$ still holds even for this different transition probability. So, I think the $$\max_p$$ is needed for the inequality to hold in the general sense.

• Could you perhaps clarify whether the variable $Y$ is the same in each display of the inequality or whether it changes depending on the first argument? Mar 25, 2022 at 13:16
• $Y$ is not the same since the input arguments are different random variables in each inequality (Different linear combinations of the same $X_i$'s) . Also, $p$ can be different for different inequalities too. Since there is a maximization over $p$. Mar 25, 2022 at 13:31
• Thanks! Did you try numerically whether the inequality might hold for all $p$ elementwise or is taking the maximum necessary? Mar 25, 2022 at 14:14
• @Steve I was wrong when I thought $H(Y)$ remains the same. (I deleted the comment to avoid misinformation). So $Y$ is not the same across different inequalities. Mar 25, 2022 at 14:45
• Sorry, maybe my second question was not clear: What I meant was whether you can fix $p$ at the start and remove the $\max_p$ in the inequalities, and whether you have numerical insight as to whether this might still hold? Mar 25, 2022 at 20:53