# 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.

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