Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This is from a book. Mention it. – Did Jul 14 '12 at 8:12
This is from "The concentration of Measure Fenomenon" by M. Ledoux. – user 1618 Jul 14 '12 at 15:45
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? – joriki Jul 28 '12 at 7:36

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

share|cite|improve this answer
One asks for an almost sure upper bound hence all the random part of the question is useless. – Did Jul 28 '12 at 8:41
I cannot get representation $g(\tau\pi)$ in terms of $g(\pi)+2(c_{\pi(I)}-c_{\pi(J)})a_{\pi}(I,J)$. Could you elaborate it, please. Thnk you very much for your help. – Nick G.H. Jul 29 '12 at 23:49
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)$.) – Did Jul 30 '12 at 9:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.