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

  • $\begingroup$ 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. $\endgroup$ – Ragib Zaman Sep 1 '11 at 9:09
  • $\begingroup$ @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. $\endgroup$ – 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}$$

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

  • 1
    $\begingroup$ Damn, you beat me to it! I had the same answer half typed up =[ lol. $\endgroup$ – Ragib Zaman Aug 30 '11 at 10:19
  • 1
    $\begingroup$ @Ragib: The moment I saw the pattern I knew this would end up a race to type it out. ;) $\endgroup$ – anon Aug 30 '11 at 10:20
  • $\begingroup$ @anon: Superb! Thank you very much. Why didn't I see that? $\endgroup$ – Derek O'Connor Aug 30 '11 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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