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

Please help me to find a Lipschitz constant.

Let $S_n$ be a group of permutations of the set $\{1, \ldots, n\}$. Let $a=(a_1, \ldots, a_{2M})$ be a real valued vector with $n$ non-zeroes entries, $M \gg n$. Consider a function $f: S_n \longrightarrow R$ as following:

$$ f(\pi)=c_k\sum_{k=0}^n\left|\sum_{i=1}^ka_{\pi(i)}-\sum_{i=k+1}^{n}a_{\pi(i)}\right|, $$ where $c_k=\frac{{n\choose k}{2M-n \choose M-k}}{2M\choose M}$.

I would like to find a Lipschitz constant, $L$, i.e. I would like to get $|f(\pi)-f(\sigma)|\leq L\, d(\pi, \sigma)$, where $d(\pi, \sigma)=\#\{i: \pi(i) \neq\sigma(i), \pi, \sigma\in S_n\}$.

I'v started by considering (for $\pi, \sigma \in S_n$) $$ |f(\pi)-f(\sigma)| \leq c_k \sum_{k=0}^n\left|\sum_{i=1}^k (a_{\pi(i)}-a_{\sigma(i)}) - \sum_{i=k+1}^n (a_{\pi(i)}-a_{\sigma(i)})\right| $$

And here I am stack.

Thank you for your help.

share|cite|improve this question
Could you clarify which norm you want to use on permutations? That is, you want to find $L$ such that $|f(\pi)-f(\sigma)|\leq L\|\pi-\sigma\|$, where $\|\cdot\|$ is your permutation norm. – Alex R. Oct 9 '12 at 19:59
Thank you. It is a distance between the permutations, $d(\pi, \sigma)$. – Michael Oct 9 '12 at 20:06
And that would be? The number of transpositions of $\pi^{-1}\sigma$? – Hagen von Eitzen Oct 9 '12 at 20:24
Sorry, I did not mentioned, the distance between two permutations is $$d(\pi, \sigma)=\#\{i: \pi(i) \neq\sigma(i), \pi, \sigma\in S_n\}$$ – Michael Oct 9 '12 at 20:38

Your Answer


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

Browse other questions tagged or ask your own question.