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.

  • 1
    This is from a book. Mention it.2012-07-14
  • 0
    This is from "The concentration of Measure Fenomenon" by M. Ledoux.2012-07-14
  • 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