4
$\begingroup$

Asymptotic Approximation for a Derangement Algorithm

I have been analyzing the complexity of a simple algorithm for randomly generating a derangement, i.e., a permutation $\pi$ with no fixed points: $\pi_i \ne i,\, i = 1,2, \ldots,n.$

The expected total work of this (Las Vegas) algorithm is $ W_T(n) = W_s(n) + \frac{1-p(n)}{p(n)}W_f(n), $ where $p(n)$ is the probability of success (a derangement is generated), $W_s(n)$ the expected work to generate a success, and $W_f(n)$ is the expected work to generate a failure.

I know that $W_s(n) = n-1$, and $p(n) = 1/e \approx 0.368$, but I'm having difficulty with $W_f(n)$. Here is what I have so far: $ W_f(n) =\sum_{k=1}^{n-2}k p_{nk}= \sum_{k=1}^{n-2}\,\prod_{i=0}^{k-1}\left(1-\frac{1}{n-i}\right). $ $W_f(n)=4.4, 49.49, 499.499, 4999.4999, 49999.49999$, for $n = 10^1, 10^2, 10^3,10^4,10^5.$

This suggests that

$ \lim_{n\rightarrow \infty} \sum_{k=1}^{n-2}\,\prod_{i=0}^{k-1}\left(1-\frac{1}{n-i}\right) = \frac{1}{2}n. $

We now have all the pieces of the first equation equation and we get

$ W_T(n) = n-1 + \frac{(1-1/e)}{1/e}\frac{n}{2} = \frac{\left( e+1\right)}{2}\,n-1 \approx 1.86n . $ Testing the algorithm shows that this is roughly correct, but I have not been able to prove the $\frac{1}{2}n$ limit above. The best I have come up with so far is $\ln(kp_{nk}) = H_n-H_{n-k},\quad W_f(n) = \sum_{k=1}^{n-2} e^{H_n-H_{n-k}}$ which goes to something like $2n-\ln n$. This does not seem correct. Any help would be very appreciated.

Derek O'Connor

  • 0
    @Ragib, Thanks for your advice. I have found a flaw in the Matlab function above. A small patch fixes it but I don't like that so I'm going to delete it.2011-09-09

1 Answers 1

4

Observe $\prod_{i=0}^{k-1}\left(1-\frac{1}{n-i}\right)=\left(1-\frac{1}{n}\right)\left(1-\frac{1}{n-1}\right)\cdots\left(1-\frac{1}{n-(k-1)}\right)$ $=\frac{n-1}{n}\cdot\frac{n-2}{n-1}\cdot\frac{n-3}{n-2}\cdot\cdots\frac{n-(k-1)-1}{n-(k-1)} $ $=\frac{1}{n}\cdot\frac{n-k}{1}$ due to massive cancellation in consecutive numerator/denominators. Hence the sum is

$\sum_{k=1}^{n-2}\left(1-\frac{k}{n}\right)=\left(\sum_{k=1}^{n-2}1\right)-\frac{1}{n}\left(\sum_{k=1}^{n-2}k\right)$ $=(n-2)-\frac{1}{n}\frac{(n-2)(n-1)}{2}$ $=\frac{n-1}{2}-\frac{1}{n}$

which matches the given calculations exactly. Note the formula for the triangle numbers above.

  • 0
    @anon: Superb! Thank you very much. Why didn't I see that?2011-08-30