The statement I am trying to prove is the following:

Given a Poisson binomial $S$ whose parameters $p=(p_1, \dots, p_n)$ are bounded by 0.5, and where $n$ is even. Proof that, $$ P(S=n/2) \leq P(B=n/2),$$ where $B$ is the binomial distribution with parameters n and 0.5.

I think it should be true, but I could not prove it...

The pmf found on Wikipedia is hard to work with. I found that $p_1 = p_2 = \dots = p_n = 0.5$ is a saddle point of $P(S=n/2)$, but I don't know if there are other stationary points inside $[0, 0.5]^n$.

Alternatively, using this answer, it is possible to bound the cmf of $S$ using the cmf of $B$, i.e., $$P(S\geq k) \leq P(B\geq k)$$ for all $k\in \{1,\dots,n\}$. But I'm not able to transfer it to the pmf.


1 Answer 1


Here is one way that seems to work:

Let $n=2p$. Using the pmf of the Poisson-Binomial distribution we have $$\mathbb{P}(S=p)=\sum_{T\subset\{1,\cdots,n\}, |T|=p}\prod_{i\in T}p_i\prod_{i\in T^c}(1-p_i).$$ This expression is linear in each $p_i$. Therefore, if all values $p_i$ are fixed except for some $p_j$ then $\mathbb{P}(S=p)$ is either increasing or deacreasing wrt $p_j$. This shows that $\mathbb{P}(S=p)$ reaches its maximum value at some point $(p_1,\cdots, p_n)$ such that $p_i=0$ or $1/2$ for all $i$. Let $E$ be the set of $i$ such that $p_i=0$. We consider that if $i\notin E$ then $p_i=1/2$. In this case, $\mathbb{P}(S=p)$ can be rewritten the following way: \begin{align*} \mathbb{P}(S=p)&=\sum_{T\subset\{1,\cdots,n\}, |T|=p, T\cap E=\emptyset}\prod_{i\in T}p_i\prod_{i\in T^c}(1-p_i) + \sum_{T\subset\{1,\cdots,n\}, |T|=p, T\cap E\neq\emptyset}\prod_{i\in T}p_i\prod_{i\in T^c}(1-p_i).\\ &= \sum_{T\subset\{1,\cdots,n\}\backslash E, |T|=p}\frac{1}{2^{n-|E|}} + 0\\ &= \binom{n-|E|}{p}\frac{1}{2^{n-|E|}}. \end{align*} If $|E|\geq 1$ then using Pascal's triangle recursion formula we get $$\binom{n-|E|}{p} + \binom{n-|E|}{p-1} = \binom{n-(|E|-1)}{p}.$$ Now, we know that $\binom{n}{k}$ is increasing wrt $k$ when $k\leq n/2$ and decreasing when $k\geq n/2$. In our case, since $p=n/2$ then $p\geq p-1 \geq \frac{n-|E|}{2}$ hence $\binom{n-|E|}{p-1}\geq \binom{n-|E|}{p}$ and thus $\binom{n-(|E|-1)}{p}\geq 2 \binom{n-|E|}{p}$ and finally $$\binom{n-(|E|-1)}{p} \frac{1}{2^{n-(|E|-1)}} \geq \binom{n-|E|}{p}\frac{1}{2^{n-|E|}}.$$ $\mathbb{P}(S=p)$ is thus maximized when $|E|=0$ and thus $$\mathbb{P}(S=p)\leq \binom{n}{p}\frac{1}{2^n} = \mathbb{P}(B=p).$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .