Skip to main content
MathOverflow

Return to Question

Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by wanderer
Bounty Started worth 100 reputation by wanderer
Added numerical analysis
Source Link
wanderer
wanderer
  • 83
  • 1
  • 6

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.

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.

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.

Source Link
wanderer
wanderer
  • 83
  • 1
  • 6

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.