also @ross2011fundamentals [Theorem 7.4]): let $Y,Y'$ be bounded variables satisfying

1.  $(Y,Y')\stackrel{d}{=}(Y',Y)$;

2.  ${\ensuremath{\mathbb{E}}}[Y'-Y|Y]=-\lambda Y$;

3.  ${\ensuremath{\mathbb{E}}}[(Y'-Y)^2|Y]\leq \lambda(bY+c)$,

for some constants $\lambda\in(0,1)$ and $b,c\geq 0$. Then for all $a>0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(Y\leq -a\right) \leq \exp\left\{-\frac{a^2}{c}\right\}& \textrm{ and } &
{\ensuremath{\mathbb{P}}}\left(Y\geq a\right) \leq  \exp\left\{-\frac{a^2}{ab+c}\right\}.\end{aligned}$$ We shall only use the first inequality. Consider the centered variable $$Y:=\sum_{i\in{\ensuremath{\mathcal{I}}}} w_{i,\pi(i)}-m,$$ and let $Y'$ be the corresponding quantity for the pairing $\pi'$ obtained from $\pi$ by performing a random switch: two indices $i,j$ are sampled uniformly at random from ${\ensuremath{\mathcal{I}}}$ without replacement, and the pairs $\{i,\pi(i)\}$, $\{j,\pi(j)\}$ are replaced with the pairs $\{i,j\}$, $\{\pi(i),\pi(j)\}$. This changes the weight by exactly $$\label{eq:Deltaij}
\Delta_{i,j}:= w_{i,j}+w_{j,i}+w_{\pi(i),\pi(j)}+w_{\pi(j),\pi(i)}-w_{i,\pi(i)}-w_{\pi(i),i}-w_{j,\pi(j)}-w_{\pi(j),j}.$$ It is not hard to see that $(\pi,\pi')\stackrel{d}{=}(\pi',\pi)$, so that (i) holds. Moreover, $$\begin{aligned}
{\ensuremath{\mathbb{E}}}[Y'-Y|\pi]& = & \frac{1}{|{\ensuremath{\mathcal{I}}}|(|{\ensuremath{\mathcal{I}}}|-1)}\sum_{i\in{\ensuremath{\mathcal{I}}}}\sum_{j\neq i} \Delta_{i,j}\\
& = & \frac{4}{|{\ensuremath{\mathcal{I}}}|(|{\ensuremath{\mathcal{I}}}|-1)}\sum_{i\in{\ensuremath{\mathcal{I}}}}\sum_{j\neq i}w_{i,j}-\frac{4}{|{\ensuremath{\mathcal{I}}}|}\sum_{i\in{\ensuremath{\mathcal{I}}}}w_{i,\pi(i)}\\
& = & -\frac{4}{|{\ensuremath{\mathcal{I}}}|}Y.\end{aligned}$$ Regarding the square $\Delta_{i,j}^2=|\Delta_{i,j}||\Delta_{i,j}|$, we may bound the first copy of $|\Delta_{i,j}|$ by $2\theta$ and the second by changing all minus signs to plus signs in (\[eq:Deltaij\]), yielding $$\begin{aligned}
{\ensuremath{\mathbb{E}}}\left[(Y'-Y)^2|\pi\right]& = & \frac{1}{|{\ensuremath{\mathcal{I}}}|(|{\ensuremath{\mathcal{I}}}|-1)}\sum_{i\in{\ensuremath{\mathcal{I}}}}\sum_{j\neq i} \Delta_{i,j}^2\\
&  \leq & \frac{8\theta}{|{\ensuremath{\mathcal{I}}}|(|{\ensuremath{\mathcal{I}}}|-1)}\sum_{i\in{\ensuremath{\mathcal{I}}}}\sum_{j\neq i}w_{i,j}+\frac{8\theta}{|{\ensuremath{\mathcal{I}}}|}\sum_{i\in{\ensuremath{\mathcal{I}}}}w_{i,\pi(i)}\\
& = & \frac{8\theta}{|{\ensuremath{\mathcal{I}}}|}\left(2m+Y\right).\end{aligned}$$ Note that taking conditional expectation with respect to $Y$ does not affect the right-hand side. Thus, (ii) and (iii) hold 