Talk:Average loop length: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:03, 4 January 2013

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)

@@ Line 1: / Line 1: @@
 ==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. --[[User:Paddy3118|Paddy3118]] 15:53, 4 January 2013 (UTC)
-:Let me try:
-:<math>P_k</math> is the probability for a sequence of length k to loop on the k-th term
-:We have <math>P_1 = 1</math>.
-:For k>1,
-:<math>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}</math>
-:The average length it then:
-:<math>\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}</math>
-: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.
-:--[[User:Grondilu|Grondilu]] 17:27, 4 January 2013 (UTC)
-:O yeah I understood my mistake.  <math>P_k = \frac{N!}{(N-k)!N^k}</math> 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.
-:--[[User:Grondilu|Grondilu]] 18:50, 4 January 2013 (UTC)