<p>I have two random variables <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>. <span class="math-container">$X$</span> follows <a href="https://en.wikipedia.org/wiki/Poisson_binomial_distribution" rel="noreferrer">Poisson-Binomial</a> distribution with parameters <span class="math-container">$\{q_1, \ldots, q_k\}$</span>. Thus, <span class="math-container">$X$</span> can take values in the set <span class="math-container">$\{0,1,\ldots,k\}$</span>.</p>
<p><span class="math-container">$Y$</span> is a binary random variable. <span class="math-container">$Y=0$</span> with probability <span class="math-container">$\frac{0.1}{1+i}$</span> when <span class="math-container">$X=i$</span>.</p>
<p>I am interested in the mutual information between <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> denoted by <span class="math-container">$I(X;Y)$</span>.</p>
<p><strong>Specifically, I have a conjecture that the mutual information <span class="math-container">$I(X;Y)$</span>
is maximum when all <span class="math-container">$q_i$</span>'s are equal which leads to a Binomial
distribution for <span class="math-container">$X$</span>.</strong></p>
<p>Can someone help me prove this? Or provide a counter example?</p>

CC BY-SA 4.0
2022-02-09T05:48:07.760Z
Do you have an intuition or justification for this conjecture?
Clement C.
CC BY-SA 4.0
2022-02-09T16:50:32.180Z
@ClementC. Yes, First of all, Binomial distribution has the maximum entropy among Poisson- binomial distributions. Also, for a given mean, the variance is maximum when all probability parameters are equal and we have a binomial distribution.

So, I am hoping somehow the symmetry can be used to claim the conjecture. ie, From a Poisson-Binomial, you can always create a BInomial with a better mutual information by mixing the sampling probabilities. I don't know how to establish this though.
wanderer
CC BY-SA 4.0
2022-02-11T04:12:46.733Z
There is a **significant** probability I messed up the "coding" in Mathematica, but, if not, it seems that a version of the conjecture is false (for a given value of $q_1$, it's maximised when all equal) in the case $k=2$: https://www.wolframcloud.com/obj/ccanonne/Published/conjecture-mi-pbd.nb (see the two plots at the end)
Clement C.
CC BY-SA 4.0
2022-02-11T04:14:57.407Z
Of course, that may not be what you had in mind (maximised for *some* value of the parameter $(q_1,\dots,q_k)$) where all $q)i$'s are equal, in which case this is not a counterexample (cf. last graph, again, which would support this version))
Clement C.
CC BY-SA 4.0
2022-02-11T04:54:16.117Z
@ClementC. I took a look at the plots. Just to make sure, if I understood it correctly; So the maximum mutual information occurs when $q_1 \approx 0.37$ (Last graph). And it seems like the optimal $q_2$ is also around 0.37 (2nd graph)? Am I correct in reading the graphs. If that's true, my conjecture holds, right?
wanderer
CC BY-SA 4.0
2022-02-11T05:09:48.713Z
yes, this is what I laboriously tried to say above. What is *not* true is that, fixing an arbitrary $q_1$, the maximum is for $q_2=q_1$. What might be true (supported by this) is that, optimizing over both $q_1,q_2$, the max is realized for some pair where they are equal.
Clement C.
CC BY-SA 4.0
2022-02-11T05:18:46.293Z
@ClementC, Yes, I am interested in joint optimization over all $q_i$'s. This also is in accordance with the intuitions I stated in my first comment. They are all focused on for a given mean $(\sum q_i)$.  So, if someone can prove that for a given mean, my conjecture holds. The extension is trivial.
wanderer
CC BY-SA 4.0
2022-02-11T07:15:54.733Z
Nitpicking: I get what you mean, but I am not so sure the reduction comes with no restriction -- there has to be some restriction (for the statement "without loss of generality, it suffices to prove it for any given mean"). For instance, $\sum_i q_i = k$ or $\sum_i q_i = 0$ are both quite... not general. :)
Clement C.
<pr.probability><it.information-theory><shannon-entropy>
Maximize the mutual information between 2 discrete random variables
wanderer
# Maximize the mutual information between 2 discrete random variables

(Asked by: username_0 on 2022-02-05)

I have two random variables $X$ and $Y$. $X$ follows [Poisson-Binomial](https://en.wikipedia.org/wiki/Poisson_binomial_distribution) distribution with parameters $\{q\_1, \ldots, q\_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$.

$Y$ is a binary random variable. $Y=0$ with probability $\frac{0.1}{1+i}$ when $X=i$.

I am interested in the mutual information between $X$ and $Y$ denoted by $I(X;Y)$.

**Specifically, I have a conjecture that the mutual information $I(X;Y)$
is maximum when all $q\_i$'s are equal which leads to a Binomial
distribution for $X$.**

Can someone help me prove this? Or provide a counter example?

**Tags:** pr.probability, it.information-theory, shannon-entropy

> **Comments:**
> **username_1**: Do you have an intuition or justification for this conjecture?  
> **username_0**: @ClementC. Yes, First of all, Binomial distribution has the maximum entropy among Poisson- binomial distributions. Also, for a given mean, the variance is maximum when all probability parameters are equal and we have a binomial distribution.  So, I am hoping somehow the symmetry can be used to claim the conjecture. ie, From a Poisson-Binomial, you can always create a BInomial with a better mutual information by mixing the sampling probabilities. I don't know how to establish this though.  
> **username_1**: There is a **significant** probability I messed up the "coding" in Mathematica, but, if not, it seems that a version of the conjecture is false (for a given value of $q_1$, it's maximised when all equal) in the case $k=2$: https://www.wolframcloud.com/obj/ccanonne/Published/conjecture-mi-pbd.nb (see the two plots at the end)  
> **username_1**: Of course, that may not be what you had in mind (maximised for *some* value of the parameter $(q_1,\dots,q_k)$) where all $q)i$'s are equal, in which case this is not a counterexample (cf. last graph, again, which would support this version))  
> **username_0**: @ClementC. I took a look at the plots. Just to make sure, if I understood it correctly; So the maximum mutual information occurs when $q_1 \approx 0.37$ (Last graph). And it seems like the optimal $q_2$ is also around 0.37 (2nd graph)? Am I correct in reading the graphs. If that's true, my conjecture holds, right?  
> **username_1**: yes, this is what I laboriously tried to say above. What is *not* true is that, fixing an arbitrary $q_1$, the maximum is for $q_2=q_1$. What might be true (supported by this) is that, optimizing over both $q_1,q_2$, the max is realized for some pair where they are equal.  
> **username_0**: @ClementC, Yes, I am interested in joint optimization over all $q_i$'s. This also is in accordance with the intuitions I stated in my first comment. They are all focused on for a given mean $(\sum q_i)$.  So, if someone can prove that for a given mean, my conjecture holds. The extension is trivial.  
> **username_1**: Nitpicking: I get what you mean, but I am not so sure the reduction comes with no restriction -- there has to be some restriction (for the statement "without loss of generality, it suffices to prove it for any given mean"). For instance, $\sum_i q_i = k$ or $\sum_i q_i = 0$ are both quite... not general. :)  

---

## 0 answers

