8
$\begingroup$

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.

$\endgroup$
7
  • $\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(1-2)+abs(2-3)+abs(3-1) = 4, rather than 2? $\endgroup$
    – Stefan Kohl
    Feb 19, 2013 at 13:46
  • 2
    $\begingroup$ You don't include abs(3-1) because 1 and 3 are not consecutive in (1,2,3). $\endgroup$
    – Ira Gessel
    Feb 19, 2013 at 14:52
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 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_manul
    Feb 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$ Feb 20, 2013 at 21:05

2 Answers 2

7
$\begingroup$

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

$\endgroup$
6
  • $\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$
    – Math_manul
    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$
    – Math_manul
    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
4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.