# Coupling a binomial - parity conditioning

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?

• 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$. – Timothy Budd Dec 16 '20 at 16:47
• That's super nice, thanks! I'll work on trying something similar for other $p$. – DJA Dec 16 '20 at 19:24
• 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. – Fedor Petrov Dec 16 '20 at 20:04
• This is a super special symmetry, though. I'm finding the case of $p \neq 1/2$ much more challenging. – DJA Dec 16 '20 at 20:19

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

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.

• thanks so much! – 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$$

• thank you! this is great. – DJA Dec 16 '20 at 22:06
• 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. – Iosif Pinelis Dec 17 '20 at 14:38