# A sum of two binomial random variables

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$$.

• An idea (I don'the know how to pursue all the way): express $f_{n, c}$ through beta functions and prove that it is concave. Then, by symmetry, the maximum is attained in the middle. Apr 17, 2020 at 6:55
• I don't know why people are voting to close. I don't think this question is more trivial than many similar ones, which get detailed answers here. Apr 20, 2020 at 10:58
• The result seems to be true, but I don't see any working monotonicity patterns. A mystery! I think it could help if you let us know how this conjecture arose. Apr 21, 2020 at 16:57
• It looks like monotonicity fails due to rounding. For a fixed $k$ the maximizing $l$ is the expectation up to rounding. Maybe one could obtain monotonicity by extending the definition to non-integer $l$. Apr 21, 2020 at 20:36

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.

• Indeed a very surprising proof. There is a small typo in the third row of proving (b): The middle term is $\mathbb{P}(X+Y = X' + Y')$. Apr 29, 2020 at 10:37