4
$\begingroup$

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)|$.

Thank you for your help.

  • 3
    Upper bound with respect to what? If $c$ is varied, there can't be an upper bound since $f$ scales with $c$. Also, what's "independently and uniformly" doing in there when all you want is an upper bound?2012-07-28

1 Answers 1

1

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]$.

  • 0
    A difference between $g(\pi)$ and $g(\tau\pi)$ occurs when some $c_n$ counted as $+c_n$ become counted as $-c_n$, or vice versa. This happens if $\tau\pi(k)\ne\pi(k)$, that is, $\pi(k)=I$ or $\pi(k)=J$, and then, $c_{\tau\pi(k)}=c_{\pi(k)}\pm(c_I-c_J)$. Finally, the difference must be counted twice because $\tau$ sends $c_I$ to $c_J$ and $c_J$ to $c_I$. (The formula with $c_{\pi(I)}-c_{\pi(J)}$ in a former version of my post applies to $g(\pi\tau)-g(\pi)$ instead of $g(\tau\pi)-g(\pi)$.)2012-07-30