If I have a binomial $X \sim B(n,p)$, and another binomial $X' \sim B(n,p)$ conditioned on $X'$ being of even parity. Is it true that there always exists a coupling for $(X,X')$ with $|X-X'| \le 1$? (i.e. for any $n$ and $p := p(n)$ possibly a function of $n$.)

It seems intuitively obvious; is there a clean proof?

  • 2
    $\begingroup$ The case $p=1/2$ is easy: first sample $X$ and if its even set $X'=X$ and if it is odd set $X' = X\pm 1$ with a minus sign chosen independently with probability $X/n$. $\endgroup$ – Timothy Budd Dec 16 '20 at 16:47
  • $\begingroup$ That's super nice, thanks! I'll work on trying something similar for other $p$. $\endgroup$ – DJA Dec 16 '20 at 19:24
  • $\begingroup$ in other words, $X=\xi_1+\ldots+\xi_n$, $X'=\xi_1+\ldots+\xi_{n-1}+(\xi_1+\ldots+\xi_{n-1} \pmod 2)$ for i.i.d 1/2-Bernoulli $\xi_i$'s. $\endgroup$ – Fedor Petrov Dec 16 '20 at 20:04
  • $\begingroup$ This is a super special symmetry, though. I'm finding the case of $p \neq 1/2$ much more challenging. $\endgroup$ – DJA Dec 16 '20 at 20:19

This is possible for all $n$ and $p$.

I start with a direct construction.

Obviously, if $X$ is even, then we should have $X'=X$. So we should construct the corresponding coupling between $Y$ and $X'$, where $Y$ is the $B(n,p)$ restricted to odd outcomes.

Choose $2n$ i.i.d. Bernoulli$(p)$ variables $\xi_1,\ldots,\xi_n;\eta_1,\ldots,\eta_n$ and condition to $$\sum (\xi_i+\eta_i) \quad \text{is odd}.$$

Denote by $\Omega$ the set of possible $2^{2n-1}$ outcomes and consider the map $\Phi:\Omega\to \Omega$: choose the minimal $i$ for which $\xi_i\ne \eta_i$ and switch $\xi_i$ and $\eta_i$. This is a measure-preserving involution. Note that $\Phi$ changes the parity of $S=\eta_1+\ldots+\eta_n$, so $S$ is even with probability $1/2$. Next, if we further condition to ($S$ is even), then $S$ becomes distributed as $X'$. Indeed, this clearly holds even we fix all $\xi_i$'s (with odd sum). Analogously, if $S$ is odd, it is distributed as $Y$.

Now our coupling: choose $\omega\in \Omega$ at random, set $\{X',Y\}=\{S(\omega), S(\Phi(\omega)\}$.

Well, now goes a boring explanation how to get this coupling using generating functions.

Let $c_0,c_2,\ldots$ be probabilities of outcomes $0,2,\ldots$ for $X'$, we have $c_0+c_2x^2+\ldots=\frac{(q+px)^n+(q-px)^n}{1+\delta^n}$, $\delta:=q-p$ (and $q=1-p$). Denote the probabilities for $Y$ by $c_1,c_3,\ldots$, then $c_1+c_3x^2+\ldots=\frac{(q+px)^n-(q-px)^n}{1-\delta^n}$.

How may our coupling between $Y$ and $X$ look like? There is no freedom: if $Y=1$, then $X'\in \{0,2\}$ with probabilities corr. $c_0$ and $c_1-c_0$ (these are not conditional probabilities, I mean, $c_1-c_0={\rm prob}(Y=1,X'=2)$ etc.) If $Y=3$, then $X'\in \{2,4\}$ with probabilities $c_2-c_1+c_0$ and $c_3-c_2+c_1-c_0$, etc. Thus what we need is that all alternating sums $c_k-c_{k-1}+c_{k-2}-\ldots$ must be non-negative, or: all coefficients of $$ F(x):=(c_0+c_1x+c_2x^2+\ldots)(1-x+x^2+\ldots) $$ must be non-negative. We have $$ F(x)=2\frac{(q+px)^n-\delta^n(q-px)^n}{(1+x)(1-\delta^{2n})}= 2\frac{((q+p)(q+px))^n-((q-p)(q-px))^n}{(1+x)(1-\delta^{2n})}=\\ 2\frac{((q^2+p^2x)+pq(1+x))^n-((q^2+p^2x)-pq(1+x))^n}{(1+x)(1-\delta^{2n})}, $$ and expanding $((q^2+p^2x)\pm pq(1+x))^n$ by Binomial we see that $F(x)$ is indeed a polynomial with non-negative coefficients.

  • $\begingroup$ thanks so much! $\endgroup$ – DJA Dec 16 '20 at 22:06

Your conjecture is true. Indeed, \begin{equation*} P_k:=P(X=k),\quad P'_{2j}:=P(X'=2j)=P_{2j}/Q,\tag{0} \end{equation*} where $k$ and $j$ are integers, and \begin{equation*} Q:=\sum_j P_{2j}. \end{equation*} Here we need to assume that $n$ is even or $p<1$, in order to have $Q>0$.

It suffices to show that for all integers $j$ there are numbers $m_j\in[0,P_{2j-1}]$ such that \begin{equation*} P'_{2j}=P_{2j}+m_j+(P_{2j+1}-m_{j+1}) \tag{1} \end{equation*} for all $j$; here, $m_j$ is the probability mass to be transported from $2j-1$ forward to $2j$, with the remaining probability mass $P_{2j-1}-m_j$ to be transported from $2j-1$ backward to $2j-2$.

If one wants to avoid mass transportation language, here is an explicit description of the desired joint distribution of $X$ and $X'$: $$P(X'=2j,X=k)= \begin{cases} P_{2j}&\text{ if }k=2j, \\ m_j&\text{ if }k=2j-1, \\ P_{2j+1}-m_{j+1}&\text{ if }k=2j+1, \\ 0&\text{ otherwise. } \end{cases}$$ for all integers $j,k$. This and (1) will indeed imply that $P(X'=2j)=P'_{2j}$ and $P(X=k)=P_k$ for all integers $j$ and $k$, as well as $P(|X'-X|\le1)=1$, as desired.

In view of (0), rewrite (1) as \begin{equation*} m_{j+1}-m_j=P_{2j}(1-1/Q)+P_{2j+1}, \end{equation*} with the initial condition $m_{-\infty}:=\lim_{j\to-\infty}m_j=0$. So, (1) can be rewritten as \begin{equation*} m_j=U_j:=\sum_{i=-\infty}^{j-1}u_i,\quad\text{where}\quad u_i:=P_{2i}(1-1/Q)+P_{2i+1}. \end{equation*} Also, $P_{2j-1}=\sum_{i=-\infty}^{j-1}(P_{2i+1}-P_{2i-1})$. So, the conditions $m_j\in[0,P_{2j-1}]$ for all integers $j$ can be rewritten as \begin{equation*} U_j\ge0\ge L_j:=\sum_{i=-\infty}^{j-1} l_i,\quad\text{where}\quad l_i:=P_{2i}(1-1/Q)+P_{2i-1}. \tag{2} \end{equation*}

Next, $U_{-\infty}=L_{-\infty}=U_{\infty}=L_{\infty}=0$. Also, the sequence $(P_k)$ is log-concave: $P_k^2\ge P_{k-1}P_{k+1}$ for all integers $k$.

So, the $u_i$'s can change the sign at most once as $i$ increases, and only from $+$ to $-$. That is, the $U_j$'s can change only from increase to decrease as $j$ increases. Since $U_{-\infty}=0=U_{\infty}$, it follows that indeed $U_j\ge0$ for all integers $j$. Similarly, $L_j\le0$ for all integers $j$. So, the inequalities (2) are proved. $\Box$

  • $\begingroup$ thank you! this is great. $\endgroup$ – DJA Dec 16 '20 at 22:06
  • 1
    $\begingroup$ It is now made clear that the reasoning holds for any distribution on $\mathbb Z$ with a log-concave density (with respect to the counting measure), provided that the probability mass of $2\mathbb Z$ is nonzero. $\endgroup$ – Iosif Pinelis Dec 17 '20 at 14:38

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.