# Asymptotic Approximation for a Derangement Algorithm

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

-
By pure coincidence I came across this post again and realized you made an edit to include another question you need help with. Unfortunately I can't help you right now, but my advice is that you should make a completely new thread on the new question. Barely anyone would be opening this question anymore, its many pages from the front page. – Ragib Zaman Sep 1 '11 at 9:09
@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. – Derek O'Connor Sep 9 '11 at 9:40

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