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