Expected number of random interval flips needed for sorting a random array

Question

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort.

Assume that $A$ is an array initialized by a random permutation on the set $I_n=\{1,2,\ldots, n\}$.

Consider the next algorithm:

While $A$ is not sorted:

• Pick two random numbers $i\leq j\in\{1,2,\ldots, n\}$ uniformly and reverse $A[i\ldots j]$.

For example, if the initial array was $A=1,4,2,3,5,6$ and the algorithm picks $i=2,j=5$ then the value of $A$ after the reversal would be $1,5,3,2,4,6$.

Notice that this algorithm halts after finite number of iterations with probability 1.

What is the expected number of iterations for the algorithm?

Answer 1

$\Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $\Omega(n!)$ iterations on average. Obviously, you need to try at least $\Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation).

Also, one can show that $O(n! \cdot n \lg n)$ is an upper bound on the number of iterations needed. Here's why. It's known that there is a constant $c$ such that composing $k=c n \lg n + o(n \lg n)$ randomly chosen transpositions gives you something that is close to a random permutation. So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant. Each one is approximately a random permutation (independent of all others). After checking $\Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order. Therefore, your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations. Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort -- thus your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.

So we know that the answer is at least $\Omega(n!)$ and at most $O(n! \cdot n \lg n)$. Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn't leave much of a gap -- it almost totally resolves the question. If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap -- but lacking clear motivation for studying this problem, it's not clear it's worthwhile to spend that level of energy on it.

---

How do we know that composing $O(n \lg n)$ random transpositions gives you something close to a random permutation? That was proven in the following paper:

Generating a Random Permutation with Random Transpositions. Persi Diaconis, Mehrdad Shahshahani. 1981.

See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.