# question involving Markov chain

Let $S_{2m}$ be the group of all permutations $\pi$ of $\{1, 2, \ldots, 2m\}$. The following transition kernel $S$ generates the random transposition walk
$$Ch(\pi, \pi’)= \begin{cases} \frac{1}{2m} & \pi’=\pi\\[10pt] \frac{2}{(2m)^2} & \pi’=\tau \pi\ \text{ for some transposition \tau}\\[10pt] 0, & \text{otherwise} \end{cases}$$
It is known that with symmetric probability measure $\mu$, the pair $(Ch, \mu)$ defines a reversible Markov chain.

Let $\tau=(I, J)$ be a random transposition, with $I, J$ chosen independentely and uniformly from $\{1, 2, \ldots, 2m\}$. Multiplication by $\tau$ results in taking a step in the chain defined by $Ch$.

All this structure is given in “The Concentration of Measure Phenomenon” by M. Ledoux.

Let $c=(c_1, c_2, \ldots, c_{2m})$ be a vector in $R^{2m}$. Define function $f:S_{2m}\longrightarrow R$ as $f(\pi):=|\sum_{k=0}^mc_{\pi(k)}-\sum_{k=m+1}^{2m}c_{\pi(k)}|$.

Question: Find the upper bound of $|f(\pi)-f(\tau \pi)|$.

Consider $g(\pi)=\sum\limits_{k=0}^mc_{\pi(k)}-\sum\limits_{k=m+1}^{2m}c_{\pi(k)}$. Then $g(\tau\pi)=g(\pi)+2\cdot (c_{I}-c_{J})\cdot a_\pi(I,J)$, where $a_\pi(I,J)=+1$ if $J\leqslant m\lt I$, $a_\pi(I,J)=-1$ if $I\leqslant m\lt J$, and $a_\pi(I,J)=0$ otherwise.
Since $f=|g|$, this yields $|f(\pi)-f(\tau\pi)|\leqslant|g(\pi)-g(\tau\pi)|=2\cdot |c_{I}-c_{J}|\cdot [a_\pi(I,J)\ne0]$.