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

  • $\begingroup$ 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. $\endgroup$
    – Ron P
    Apr 17, 2020 at 6:55
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 20, 2020 at 10:58
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 21, 2020 at 16:57
  • $\begingroup$ 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$. $\endgroup$
    – Ron P
    Apr 21, 2020 at 20:36

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

  • 1
    $\begingroup$ 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')$. $\endgroup$ Apr 29, 2020 at 10:37
  • $\begingroup$ @DieterKadelka: Thanks, corrected! $\endgroup$
    – esg
    Apr 29, 2020 at 12:54
  • $\begingroup$ Thanks, @esg! Very slick! $\endgroup$
    – Ron P
    Apr 30, 2020 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.