0

I'm looking for something I can cite. Published work. Computationally, it seems that the average number of times the order changes in an array of random numbers of size $n$ is $$2\cdot\frac{n-2}{3}.$$ At least this works for $n=2,3,4,5,\dots$. Thoughts?

vitamin d
  • 5,783
Elliot Bendoly
  • 1
  • For example, an array of two numbers is either strictly ascending or descending. An array of 3 numbers has on average an order change of 2/3 per possible sequence, since it could be [1,2,3] (0 order changes), [1,3,2] (1 order change), [2,1,3] (1 order change), [2,3,1] (1), [3,1,2] (1), [3,2,1] (0). 4 order changes observed across 6 sequences. When n is 4, there are 32 order changes across 24 possible sequences (4/3 on average). For n of 5, 240 order changes across 120 sequences (2 on avg). Seems to keep going up by +2/3 on avg per unit increase in n. – Elliot Bendoly Mar 21 '21 at 21:15
  • The answer to the question depends on what exactly do you mean by random numbers. Are the numbers distributed uniformly in a certain range? Are they independent? Are they just the first $n$ natural numbers in a random permutation (where each permutation has the same probability)? – michalis vazaios Mar 21 '21 at 21:51
  • Yes just the first n natural numbers in a random permutation. No duplicates. For this purpose we will assume that all permutations have equal probability. – Elliot Bendoly Mar 21 '21 at 21:53

2 Answers2

1

This follows immediately from Linearity of Expectation.

Let $\{a_1, \cdots, a_n\}$ denote a permutation, selected uniformly at random.

Each of the positions $i\in \{3, \cdots, n\}$ could represent an order change, Let $X_i$ denote the indicator variable for that event. The $E[X_i]=\frac 23$ since exactly $2$ out of the six possible orders of $\{a_{i-2},a_{i-1},a_i\}$ fail to change order. But then $$E=E\left[\sum X_i\right] = \sum E[X_i]=\frac 23\times (n-2)$$ and we are done.

lulu
  • 70,402
0

Yes your intuition is correct. Think of having the permutation $p = (2, 1, 3, 5, 4)$ of the elements $(1, 2, 3, 4, 5)$. There are two changes of order. If you plot your permutation (like in the image) and the indices of the permutation you will see that the changes of order are at "peaks" or "bottoms" of the plot.

enter image description here

The answer lies to finding a way to compute the expected number of these "bottoms" and "peaks" (excluding the first and the last element of the permutation).

There are $n-2$ spots where a "peak" or "bottom" can occur.

A "peak" occurs at a given index $i$ of the permutation $p$ with probability $1/3$. This is because the probability of $max(p(i-1), p(i), p(i+1)) = p(i)$ is $1/3$.

Using the same argument, one can see that a "bottom" occurs at index $i$ with probability $1/3$.

A "peak" can't be a "bottom" at the same time (and the opposite), so the expected number of "peaks" and "bottoms" is:

$(n-2)*(\frac{1}{3}+\frac{1}{3}) = 2\frac{n-2}{3}$

michalis vazaios
  • 1,252