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?
 A: 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.
A: 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$
