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?



Coupling a binomial - parity conditioning
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.


