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.

  • $\begingroup$ 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? $\endgroup$
    – Steve
    Mar 25, 2022 at 13:16
  • $\begingroup$ $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$. $\endgroup$
    – wanderer
    Mar 25, 2022 at 13:31
  • $\begingroup$ Thanks! Did you try numerically whether the inequality might hold for all $p$ elementwise or is taking the maximum necessary? $\endgroup$
    – Steve
    Mar 25, 2022 at 14:14
  • $\begingroup$ @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. $\endgroup$
    – wanderer
    Mar 25, 2022 at 14:45
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Mar 25, 2022 at 20:53


Your Answer

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