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)

O yeah I understood my mistake. $P_{k}={\frac {N!}{(N-k)!N^{k}}}$ or something like that because you don't only want to avoid repeating the first term before the k-th, you also want to avoid all preceding ones.

--Grondilu 18:50, 4 January 2013 (UTC)