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(12)+abs(23)=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.

$\begingroup$ 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(12)+abs(23)+abs(31) = 4, rather than 2? $\endgroup$– Stefan Kohl ♦Feb 19, 2013 at 13:46

2$\begingroup$ You don't include abs(31) because 1 and 3 are not consecutive in (1,2,3). $\endgroup$– Ira GesselFeb 19, 2013 at 14:52

3$\begingroup$ You could possibly compute these finite distributions recursively, by considering how the absolutevalue sum increases when you insert $N$ into a permutation of $\{1,\dots,N1\}$. Such an approach might also lead to a proof of a central limit theorem, if you're lucky. $\endgroup$– Greg MartinFeb 19, 2013 at 18:39

$\begingroup$ 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. $\endgroup$– Math_manulFeb 19, 2013 at 22:19

2$\begingroup$ 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. $\endgroup$– Mark MeckesFeb 20, 2013 at 21:05
2 Answers
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 $xy$ is $$ \int_{x=0}^1 \left(\frac{x^2}{2} + \frac{(1x)^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^21)/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+(n2)/3$, or $(n+1)/3$. Since we compute this for $n1$ consecutive pairs, linearity of expectation tells us that the expected sum is $(n1)(n+1)/3$, or $(n^21)/3$.

$\begingroup$ 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? $\endgroup$ Feb 19, 2013 at 22:31

$\begingroup$ In each cycle distances are random and uniformly distributed. $\endgroup$ Feb 20, 2013 at 3:52

$\begingroup$ Alexey, could you please comment what do you mean by cycle? $\endgroup$ Feb 20, 2013 at 6:07

$\begingroup$ Yes, the permutations were generated randomly. The histogram represents 1,000,000 trials. $\endgroup$ Feb 20, 2013 at 8:12

1$\begingroup$ 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. $\endgroup$ Feb 22, 2013 at 19:55
Andrew King pointed out that $E[X]$ is $(n^21)/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}^{N1} \delta(i)$.
$$\begin{eqnarray}X^2 &=& \bigg(\sum_{i=1}^{N1} \delta(i)\bigg)^2 \newline &=& \sum_{i=1}^{N1} \delta(i)^2 + 2 \sum_{i=1}^{N2} \delta(i)\delta(i+1) + \sum_{ij\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 $(N1)E[\delta(1)^2]$, $2(N2)E[\delta(1)\delta(2)]$, and $((N2)(N3))E[\delta(1)\delta(3)].$
$$\begin{eqnarray}E[\delta(1)^2] &=& \frac{1}{N(N1)} ~\sum_{a,b} (ba)^2 \newline &=& \frac{1}{N(N1)} \frac{N^4N^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(N1)(N2)} \sum_{a,b,c~ \text{distinct}} bacb \newline &=& \frac{1}{N(N1)(N2)}\bigg(\sum_{a,b,c} bacb  \sum_{a,b,c  a=c} (ba)^2 \bigg) \newline &=& \frac{1}{N(N1)(N2)} \bigg( \frac{7N^5  15N^3  8N}{60}  \frac{N^4N^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(N1)(N2)(N3)} \sum_{a,b,c,d ~ \text{distinct}} badc\newline &=& \frac{1}{N(N1)(N2)(N3)} \bigg( \sum_{a,b,c,d} badc \newline & &  4 \sum_{a,b,c,d  b=d} bacb + 2 \sum_{a,b,c,da=c,b=d} (ba)^2 \bigg) \newline &=& \frac{1}{N(N1)(N2)(N3)} \bigg( \frac{N^62N^4 + N^2}{9} \newline & &  4\frac{7N^510N^415N^3+10N^2+8N}{60}+ 2 \frac{N^4N^2}{6} \bigg) \newline &=& \frac{5N^5  21 N^4 + 35N^3+45N^240N 24}{45(N1)(N2)(N3)} \newline &=& \frac{5N^416N^3+19N^2+64N+24}{45(N2)(N3)}\end{eqnarray}$$
If I calculated correctly, then
$$\begin{eqnarray}E[X^2] &= &\frac{N^3N}{6} + \frac{7N^33N^218N8}{30} \newline & & + \frac{5N^416N^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.

$\begingroup$ Expectation and variance of the sum over the ascent lengths are also investigated here: kam.mff.cuni.cz/~kamserie/serie/clanky/2005/s757.ps $\endgroup$ Aug 24, 2018 at 9:42