Lower bound for the distribution of the sum of independent Bernoulli variables ( not i.i.d)

Question

Suppose we have $X_1,\cdots,X_n$ be independent Bernoulli random variables with $n$ odd, $P(X_i=1)=p_i$ and $p_i \in [1/2,1]$ for all $i=1,\cdots,n$. I want to prove that: \begin{equation} P(\sum_{i=1}^n X_i\geq\frac{n+1}{2}) \geq \frac{\sum_{i=1}^np_i}{n} \end{equation} This translates to the following statement: The probability that the majority of the $X_i$ are $1$ is bigger than or equal to the average of the probabilities. I strongly believe this is true, but I am not sure how a probabilistic proof would go, it seems that a reverse Markov inequality or Jensen's inequality can not give me this result. Any help would be greatly appreciated!

Answer 1

The inequality suggested indeed holds, but the only proof I found takes some work.

Let ${\bf p}:=(p_1,\ldots,p_n)$ and $S:=\sum_{i =1}^n X_i$. Define \begin{equation} f({\bf p}):={\mathbb P}_{\bf p}\Bigl(S \geq\frac{n+1}{2}\Bigr) - \frac{\sum_{i=1}^np_i}{n}\,, \end{equation} so the goal is to show that $f$ is nonnegative on the cube $Q=[1/2,1]^n$.

Since $f$ is continuous on the compact set $Q$, it attains a minimum there. Denote $S_{-k}=S-X_k$. Observe that $f$ is a polynomial in the variables $p_k$, and the first term in its definition is the probability of the increasing event $\{S \ge (n+1)/2\} \,.$

Thus by Russo's formula [1], [2] for the derivative of the probability of an increasing event, or by direct differentiation, $$\frac{\partial f}{\partial p_k}({\bf p})={\mathbb P}_{\bf p}\Bigl(S_{-k}=\frac{n-1}{2}\Bigr) - \frac{1}{n} $$ $$={\mathbb P}_{\bf p}\Bigl(S_{-k} \ge \frac{n-1}{2}\Bigr) - {\mathbb P}_{\bf p}\Bigl(S_{-k} \ge \frac{n+1}{2}\Bigr)-\frac{1}{n}\,. $$ A second application of Russo's formula yields that $$\frac{\partial^2 f}{\partial^2 p_k}({\bf p}) ={\mathbb P}_{\bf p}\Bigl(S_{-k} =\frac{n-3}{2}\Bigr) - {\mathbb P}_{\bf p}\Bigl(S_{-k} = \frac{n-1}{2}\Bigr) \,. \tag{*} $$ By a Theorem of Darroch [3], reproved in [4] (See also [5] for the most convenient reference) the distribution of the Poisson-Binomial variable $S_{-k}$ is unimodal, with one or two adjacent modes (=peaks). Moreover, its lower mode differs by at most $1$ from its mean $${\mathbb E}(S_{-k})=\sum_{i \ne k} p_i \ge \frac{n-1}{2} \,.$$

Therefore, the right hand side of $(*)$ is non-negative, so it follows from $(*)$ that $f$ is concave in each variable $p_k$ separately.

(Remark: In [6] it is shown that the distribution of $S_{-k}$ is strictly log concave, which implies that $f$ is strictly concave in each variable, but we do not need that.)

Thus $f$ attains its minimum at some extreme point ${\bf p^*}$ of $Q$ where $p_k^* \in \{1/2,1\}$ for all $k$. Given such ${\bf p^*}$ where $p^*_k =1/2$ for exactly $\ell$ values of $k$, we find that $$f({\bf p^*})=\mathbb P\Bigl(\text{Bin}(\ell,1/2) \ge \frac{n+1}2-(n-\ell)\Bigr)-\frac{n-\ell+\ell/2}{n}$$ $$ = \frac{\ell}{2n}-\mathbb P\Bigl(\text{Bin}(\ell,1/2) \le \frac{n-1}2-(n-\ell)\Bigr) $$ $$\ge \frac{\ell}{2n}-\mathbb P\Bigl(\text{Bin}(\ell,1/2) \le \frac{\ell-1}{2}\Bigr) \ge 0$$ by unimodality of the binomial coefficients.

[1] https://arxiv.org/pdf/1102.5761.pdf page 29

[2] L. Russo, An approximate zero-one law, Zeitschrift fur Wahrscheinlichkeitstheorie und Verwandte Gebiete 61 (1982), 129–139.

[3] J. N. Darroch. On the distribution of the number of successes in independent trials. Ann. Math. Statist., 35, 1964.

[4] S. M. Samuels. On the number of successes in independent trials. Ann. Math. Statist., 36:1272–1278, 1965.

[5] https://arxiv.org/pdf/1908.10024.pdf eq. (2.2)

[6] http://www3.stat.sinica.edu.tw/statistica/oldpdf/A3n23.pdf eq. (20)