Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's consider all possible permutations of N numbers. Suppose for each permutation we calculate the sum of absolute differences between consecutive elements. Thus, for (1,2,3) one would have abs(1-2)+abs(2-3)=2. Is it possible to obtain a distribution of such sums for given N? For instance, for N=3 one would have 3!=6 permutations and possible sums as 2 and 3. The number of sums of 2 is 2 and for 3 it's equal 4.

share|improve this question
    
What do you mean by "the sum of absolute differences between consecutive elements"? -- So for example why don't you get for (1,2,3) abs(1-2)+abs(2-3)+abs(3-1) = 4, rather than 2? –  Stefan Kohl Feb 19 '13 at 13:46
2  
You don't include abs(3-1) because 1 and 3 are not consecutive in (1,2,3). –  Ira Gessel Feb 19 '13 at 14:52
3  
You could possibly compute these finite distributions recursively, by considering how the absolute-value sum increases when you insert $N$ into a permutation of $\{1,\dots,N-1\}$. Such an approach might also lead to a proof of a central limit theorem, if you're lucky. –  Greg Martin Feb 19 '13 at 18:39
    
That's right. The consecutive elements means elements with indexes i and i+1, i+1 and i+2 and so on, where i runs from 1 to N. Therefore, elements with indexes 1 and N are not consecutive. –  Math_manul Feb 19 '13 at 22:19
2  
For large N asymptotics, the result of Zhao, Bai, Chao, and Liang (which I haven't seen myself) mentioned in mathoverflow.net/questions/57629/… may give a proof of the normal limit theorem suggested by Andrew's histogram. –  Mark Meckes Feb 20 '13 at 21:05

2 Answers 2

Here is a histogram for length 100. It seems to be normally distributed around $100^2 / 3$, which should put you on the scent, in spite of a complete absence of proof (see edit below).

This is not at all surprising, since if $x$ and $y$ are drawn uniformly at random from the interval $[0,1]$, the expected value of $|x-y|$ is $$ \int_{x=0}^1 \left(\frac{x^2}{2} + \frac{(1-x)^2}{2}\right) = \frac 13. $$ Maybe turning this fact into a proof is very straightforward; maybe it is tricky.

Edit: I should note that the expected value of $(n^2-1)/3$ actually is very easy to prove; it is just the distribution that might be tricky.

One way to generate a random permutation $\pi$ is to choose $n$ reals $r(i)$ uniformly at random from $[0,1]$. Now, what is the expected value of $|\pi(i) - \pi(i+1)|$? It is simply the expected number of $r(j)$ between $r(i)$ and $r(i+1)$, plus one. Because the expected difference between $r(i)$ and $r(i+1)$ is $1/3$, this is $1+(n-2)/3$, or $(n+1)/3$. Since we compute this for $n-1$ consecutive pairs, linearity of expectation tells us that the expected sum is $(n-1)(n+1)/3$, or $(n^2-1)/3$.

share|improve this answer
    
Thank you! This what I suspected. Indeed I've tried to calculate exact distributions for small cases, up to N=10 and tried to find dependencies. It looks like some kind of fluctuations around binomial coefficients. For instance, in case of N=5 the distribution is (2,4,14,32,18,28,14,8). I just thought, could it be reduced to a problem of partitioning of integer number N... P.S. Did you obtain your graph from random sampling from permutations? –  Math_manul Feb 19 '13 at 22:31
    
In each cycle distances are random and uniformly distributed. –  Alexey Ustinov Feb 20 '13 at 3:52
    
Alexey, could you please comment what do you mean by cycle? –  Math_manul Feb 20 '13 at 6:07
    
Yes, the permutations were generated randomly. The histogram represents 1,000,000 trials. –  Andrew D. King Feb 20 '13 at 8:12
1  
Take real numbers $r(1)\ldots r(n)$ chosen uniformly from $[0,1]$. Then construct a permutation $\pi$ with the property that for all $i$, $\pi(i) < \pi(j)$ if and only if $r(i)<r(j)$. Since the random reals are independently identically distributed and all distinct with probability 1, $\pi$ is a uniformly random permutation. In fact, we do not need to choose uniformly from $[0,1]$ -- we only need i.i.d. and distinct with probability 1. But for the purposes of the proof, the uniform distribution is appropriate. –  Andrew D. King Feb 22 '13 at 19:55

Andrew King pointed out that $E[X]$ is $(n^2-1)/3$.

So, to calculate the variance $E[X^2] - E[X]^2$ we need to find $E[X^2]$.

Let $\delta(i) = |\pi(i+1)-\pi(i)|$, so $X = \sum_{i=1}^{N-1} \delta(i)$.

$$\begin{eqnarray}X^2 &=& \bigg(\sum_{i=1}^{N-1} \delta(i)\bigg)^2 \newline &=& \sum_{i=1}^{N-1} \delta(i)^2 + 2 \sum_{i=1}^{N-2} \delta(i)\delta(i+1) + \sum_{|i-j|\gt 1} \delta(i)\delta(j) \end{eqnarray}$$

We can compute the expected values of each of these terms to find $E[X^2]$. By symmetry, we only need to find $(N-1)E[\delta(1)^2]$, $2(N-2)E[\delta(1)\delta(2)]$, and $((N-2)(N-3))E[\delta(1)\delta(3)].$

$$\begin{eqnarray}E[\delta(1)^2] &=& \frac{1}{N(N-1)} ~\sum_{a,b} (b-a)^2 \newline &=& \frac{1}{N(N-1)} \frac{N^4-N^2}{6} \newline &=&\frac{n^2+n}{6}\end{eqnarray}$$

I used Mathematica for the sums.

$$\begin{eqnarray} E[\delta(1)\delta(2)] &=& \frac{1}{N(N-1)(N-2)} \sum_{a,b,c~ \text{distinct}} |b-a||c-b| \newline &=& \frac{1}{N(N-1)(N-2)}\bigg(\sum_{a,b,c} |b-a||c-b| - \sum_{a,b,c | a=c} (b-a)^2 \bigg) \newline &=& \frac{1}{N(N-1)(N-2)} \bigg( \frac{7N^5 - 15N^3 - 8N}{60} - \frac{N^4-N^2}{6} \bigg)\newline &=& \frac{7N^2+11N+4}{60}\end{eqnarray}$$

The diagonal terms evaluate to $0$ or resemble the first sum.

$$\begin{eqnarray} E[\delta(1)\delta(3)] &=& \frac{1}{N(N-1)(N-2)(N-3)} \sum_{a,b,c,d ~ \text{distinct}} |b-a||d-c|\newline &=& \frac{1}{N(N-1)(N-2)(N-3)} \bigg( \sum_{a,b,c,d} |b-a||d-c| \newline & & - 4 \sum_{a,b,c,d | b=d} |b-a||c-b| + 2 \sum_{a,b,c,d|a=c,b=d} (b-a)^2 \bigg) \newline &=& \frac{1}{N(N-1)(N-2)(N-3)} \bigg( \frac{N^6-2N^4 + N^2}{9} \newline & & - 4\frac{7N^5-10N^4-15N^3+10N^2+8N}{60}+ 2 \frac{N^4-N^2}{6} \bigg) \newline &=& \frac{5N^5 - 21 N^4 + 35N^3+45N^2-40N -24}{45(N-1)(N-2)(N-3)} \newline &=& \frac{5N^4-16N^3+19N^2+64N+24}{45(N-2)(N-3)}\end{eqnarray}$$

If I calculated correctly, then

$$\begin{eqnarray}E[X^2] &= &\frac{N^3-N}{6} + \frac{7N^3-3N^2-18N-8}{30} \newline & & + \frac{5N^4-16N^3+19N^2+64N+24}{45} \newline &=& \frac{10N^4+4N^3+29N^2+59N+24}{90}\end{eqnarray}$$

$$\begin{eqnarray}\text{Var}[X] &=& E[X^2] -E[X]^2 \newline &=& \frac{4N^3+49N^2+59N+14}{90} \end{eqnarray}$$

For $N=100$, the standard deviation is $\sqrt\frac{249773}{5}=223.505$.

I believe a similar (but simpler) technique can be used to approximate higher moments of $X$. The dominant term is where no differences are adjacent, and the moments should be approximately the same as for random functions to $\lbrace 1, ..., n \rbrace$ instead of permutations. I think the method of moments would allow one to prove that the distribution is asymptotically normal.

share|improve this answer

Your Answer

 
discard

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.