Lower bound for the distribution of the sum of independent Bernoulli variables ( not i.i.d) 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!
 A: 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)
