Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
a) By a random derangement, presumably you mean a derangement selected uniformly at random? b) The expression "arbitrary permutation" appears to imply that the result may depend on the initial permutation. Did you mean a permutation selected uniformly at random there, too? –  joriki Jan 16 '13 at 9:15
    
Have you written up a program to check this for $k = 3, 4, 5$? –  Benjamin Dickman Jan 16 '13 at 10:37
1  
If composing two uniformly randomly selected derangements would lead to a uniform distribution of the derangement of the resulting non-fixed points, one might obtain a tractable recursion relation, but this doesn't seem to be the case in general. The $4$-derangements resulting from composing two $5$-derangements are distributed uniformly, and so are the $5$-derangements resulting from composing two $6$-derangements, but the $4$-derangements resulting from composing two $6$-derangements are not. –  joriki Jan 16 '13 at 11:26
    
@joriki: yes to both questions –  lyj Jan 16 '13 at 15:32
    
@lyj: Please clarify the question itself (there's an edit link underneath it); people shouldn't have to read through the comments to understand the question. a) is clear enough, but b) is a real ambiguity. –  joriki Jan 16 '13 at 16:10

1 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$:

plot of logarithmic fit

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

share|improve this answer
1  
Thanks - I'm more interested in an analytic approach, but this might give some way to start; if you don't mind my asking, why exactly does this seem intractable to you? –  lyj Jan 16 '13 at 21:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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