A sum of two binomial random variables

Question

Let $p\in(0,1)$, $n$ a positive even integer, $k,l\in\{0,\dots,n\}$, and $X_k\sim \text{Binomial}(k,p)$, $Y_{n-k}\sim \text{Binomial}(n-k,1-p)$ independent random variables. I would like to prove that $$ \Pr(X_k+Y_{n-k}=l)\leq\Pr(X_{n/2}+Y_{n/2}=n/2). $$

This question can be stated analytically. Setting $c=(1-p)/p$, define: $$ f_{n,c}(k,l)=c^{l+k}\sum_{i=\max(0,k+l-n)}^{\min(k,l)}\binom{k}{i}\binom{n-k}{l-i}c^{-2i}. $$ Prove that $f_{n,c}$ attains its maximum at $k=l=n/2$, for any even $n$ and $c>0$.

Answer 1

Here is a (surprising) proof using Cauchy-Schwarz and "rearrangement". The following lemma will be the key.

Lemma : Let $X,Y$ be independent integer-valued rvs, then \begin{align*} (a)\; &\mbox{ for any } z: \;\mathbb{P}(X+Y=z)^2\leq \big(\sum_x\mathbb{P}(X=x)^2\big)\,\big(\sum_y \mathbb{P}(Y=y)^2\big)\\ (b)\; &\sum_z\mathbb{P}(X-Y=z)^2=\sum_z\mathbb{P}(X+Y=z)^2\end{align*} Proof: (a) apply Cauchy-Schwarz to $\mathbb{P}(X+Y=z)=\sum_x \mathbb{P}(X=x)\mathbb{P}(Y=z-x)$

(b) let $(X^\prime,Y^\prime)$ be distributed as $(X,Y)$, and independent of $(X,Y)$. Then \begin{align*} \sum_z\mathbb{P}(X-Y=z)^2=\mathbb{P}(X-Y=X^\prime-Y^\prime)=\mathbb{P}(X-X^\prime=Y-Y^\prime)\\ \sum_z\mathbb{P}(X+Y=z)^2=\mathbb{P}(X+Y=X^\prime+Y^\prime)=\mathbb{P}(X-X^\prime=Y^\prime-Y) \end{align*} Since $Y-Y^\prime$ and $Y^\prime-Y$ are identically distributed, and independent of $(X,X^\prime)$ the right hand sides above are equal. End Proof

Now to your question above. Let $n=2m$. We have to show that \begin{align*} \mathbb{P}(X_k+Y_{2m-k}=\ell)\leq \mathbb{P}(X_m+Y_m=m)\end{align*}For the right hand side above we have (using 1. below) \begin{align*} \mathbb{P}(X_m+Y_m=m)=\mathbb{P}(X_m=X_m^\prime)=\sum_l \mathbb{P}(X_m=l)^2\end{align*} To transform the left hand side, observe that well known properties of the binomial distribution give: \begin{align} 1.\; &Y_k \mbox{ is distributed as}\; k-X^\prime_k, \mbox{where $X_k^\prime$ is distributed as $X_k$,}\\&\mbox{ and independent of $X_k$}\\ 2.\; &\mbox{ $X_{m+j}$ resp. $Y_{m+j}$ are distributed as $X_m+X_j$ resp. $Y_m+Y_j$, where}\\ &\mbox{ the summands are independent} \end{align} Using 1. gives that $\sum_l \mathbb{P}(X_m=l)^2=\sum_l \mathbb{P}(Y_m=l)^2$ and further that $$ \mathbb{P}(X_k+Y_{2m-k}=\ell)=\mathbb{P}(X_{2m-k}+Y_k=2m-\ell)\;,$$ so we may w.l.o.g. assume that $k\leq m$. Using 1. and 2. we have $$\mathbb{P}(X_k+Y_{2m-k}=\ell)=\mathbb{P}(X_k-X_{m-k}+Y_m=\ell+k-m)$$ where $X_k,X_{m-k}$ and $Y_m$ on the right hand side are independent.

Using part (a) of the lemma (with $X=X_{k}-X_{m-k}$ and $Y=Y_m$) gives $$\mathbb{P}(X_k+Y_{2m-k}=z)^2 \leq \big(\sum_x \mathbb{P}(X_k-X_{m-k}=x)^2\big)\big(\sum_y\mathbb{P}(Y_m=y)^2\big)$$ Finally using part (b) of the lemma on the first factor gives $$\sum_{x}\mathbb{P}(X_k-X_{m-k}=x)^2=\sum_x\mathbb{P}(X_k+X_{m-k}=x)^2=\sum_x\mathbb{P}(X_m=x)^2$$ so that ultimately $$\mathbb{P}(X_k+Y_{n-k}=z)^2\leq \big(\sum_x \mathbb{P}(X_m=x)^2\big)\big(\sum_y\mathbb{P}(Y_m=y)^2\big)=\big(\sum_x \mathbb{P}(X_m=x)^2\big)^2\;,$$ as desired.