Talk:Average loop length

Analytical formula?

Hi, the task needs the analytical formula to be stated as part of the task description rather than leaving it to be discovered. --Paddy3118 15:53, 4 January 2013 (UTC)

Let me try:

$P_{k}$ is the probability for a sequence of length k to loop on the k-th term

We have $P_{1}=1$.

For k>1,

$P_{k}={\frac {N(N-1)^{k-2}}{N^{k}}}={\frac {(N-1)^{k-2}}{N^{k-1}}}={\frac {1}{N}}(1-{\frac {1}{N}})^{k-2}$

The average length it then:

$\langle L\rangle =\sum _{k=1}^{N}P_{k}\,k=1+\sum _{k=2}^{N}k{\frac {(N-1)^{k-2}}{N^{k-1}}}=1+{\frac {1}{N}}\sum _{k=2}^{N}k(1-{\frac {1}{N}})^{k-2}$

I doubt this is the correct formula as it does not give the same numerical result as the Perl6 code. It's also very different as it does not have any factorial in it. I must have missed something.

--Grondilu 17:27, 4 January 2013 (UTC)