0
$\begingroup$

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.

  • 0
    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\}$2012-10-09

0 Answers 0