Expected Number of Steps to Order First n Integers

Question

Suppose we begin with a random permutation of the first $n$ integers. At each step, we do the following:

1. Leave the integers already in the correct position where they are

2. For the remaining integers, say $a_1, a_2, \ldots, a_{k},$ perform a (random) derangement (in other words, $\sigma$ has no fixed points) $\sigma: \{1, 2, \ldots, k\} \to \{1, 2, \ldots, k\}$ on the set of indices, i.e. take $\{a_1, a_2, \ldots, a_{k}\}$ to $\{a_{\sigma(1)}, a_{\sigma(2)},\ldots, a_{\sigma(k)}\}.$

Repeat this until we arrive at the correct ordering, namely $\{1, 2, 3, \ldots, n\}.$ What is the expected number of steps for this process?

Example: If you start with the permutation $\{2, 1, 4, 3\},$ then there are $9$ possibilities for the next step (by composing with a derangement), namely:$\{1, 2, 3, 4\}, \{1, 3, 2, 4\}, \{1, 4, 3, 2\}, \{3, 2, 1, 4\},$ $\{3, 4, 2, 1\}, \{3, 4, 1, 2\}, \{4, 2, 3, 1\}, \{4, 3, 1, 2\},$ and $\{4, 3, 2, 1\}.$

If, instead, we had started with $\{1, 3, 4, 2\},$ then the possibilities would be $\{1, 2, 3, 4\}$ and $\{1, 4, 2, 3\}.$

See AoPS for the original discussion of this problem. It's not difficult to write a recursion for $E_n$ in terms of $E_{D_i},$ where $E_{D_i}$ is the expected number of steps given that we begin with precisely $(n-i)$ fixed points. However, the structure of each derangement plays a role as well, so the problem becomes extremely complicated, even for small values of $n.$

Answer 1

This looks like it might be intractable analytically; here are some numerical results. The expected number of steps if you use all permutations, not just derangements, is $n-1$ (not $n$ as claimed in the page you link to), and this will be slightly reduced by using only derangements, so it makes sense to look at the difference between $n-1$ and the expected number of steps. I estimated this (using this code) for $n$ from $1$ to $50$:

 1 : 0.00000 +- 0.00000
 2 : 0.50192 +- 0.00158
 3 : 0.83127 +- 0.00335
 4 : 1.07628 +- 0.00444
 5 : 1.28974 +- 0.00512
 6 : 1.46849 +- 0.00578
 7 : 1.61585 +- 0.00638
 8 : 1.75889 +- 0.00695
 9 : 1.87796 +- 0.00753
10 : 1.95726 +- 0.00807
11 : 2.07798 +- 0.00850
12 : 2.14687 +- 0.00902
13 : 2.24062 +- 0.00949
14 : 2.30053 +- 0.00994
15 : 2.37832 +- 0.01036
16 : 2.43386 +- 0.01082
17 : 2.47943 +- 0.01120
18 : 2.54770 +- 0.01160
19 : 2.62030 +- 0.01195
20 : 2.65276 +- 0.01232
21 : 2.69632 +- 0.01271
22 : 2.76734 +- 0.01302
23 : 2.80838 +- 0.01335
24 : 2.86145 +- 0.01367
25 : 2.88955 +- 0.01409
26 : 2.93403 +- 0.01440
27 : 3.00107 +- 0.01468
28 : 2.97926 +- 0.01501
29 : 3.04811 +- 0.01525
30 : 3.05974 +- 0.01559
31 : 3.09163 +- 0.01586
32 : 3.12180 +- 0.01621
33 : 3.17440 +- 0.01649
34 : 3.22252 +- 0.01677
35 : 3.22535 +- 0.01710
36 : 3.27475 +- 0.01736
37 : 3.25347 +- 0.01760
38 : 3.30337 +- 0.01794
39 : 3.30125 +- 0.01815
40 : 3.35362 +- 0.01837
41 : 3.36112 +- 0.01858
42 : 3.41845 +- 0.01889
43 : 3.41788 +- 0.01919
44 : 3.44682 +- 0.01935
45 : 3.51645 +- 0.01960
46 : 3.49307 +- 0.01987
47 : 3.54873 +- 0.02011
48 : 3.56090 +- 0.02035
49 : 3.57704 +- 0.02063
50 : 3.56751 +- 0.02087

The results are well fitted by a function of the form $a+\log n$, with the best fit given by $a\approx-0.32$. Here's a plot of the results together with $\log n-0.32$:

Thus asymptotically the expected number of steps appears to be approximately $n-\log n-0.68$.