Average loop length

Average loop length
You are encouraged to solve this task according to the task description, using any language you may know.

Let f be a randomly chosen mapping from the numbers 1..N to the numbers 1..N. At some point, the sequence 1, f(1), f(f(1))... will contain a repetition, a number that occurring for the second time in the sequence.

Write a program or a script that estimates, for each N, the average length until the first such repetition.

Also calculate this expected length using an analytical formula, and optionally compare the simulated result with the theoretical one.

This problem comes from the end of Donald Knuth's Christmas tree lecture 2011.

Example of expected output:

 N    average    analytical    (error)
===  =========  ============  =========
  1     1.0000        1.0000  (  0.00%)
  2     1.4992        1.5000  (  0.05%)
  3     1.8784        1.8889  (  0.56%)
  4     2.2316        2.2188  (  0.58%)
  5     2.4982        2.5104  (  0.49%)
  6     2.7897        2.7747  (  0.54%)
  7     3.0153        3.0181  (  0.09%)
  8     3.2429        3.2450  (  0.07%)
  9     3.4536        3.4583  (  0.14%)
 10     3.6649        3.6602  (  0.13%)
 11     3.8091        3.8524  (  1.12%)
 12     3.9986        4.0361  (  0.93%)
 13     4.2074        4.2123  (  0.12%)
 14     4.3711        4.3820  (  0.25%)
 15     4.5275        4.5458  (  0.40%)
 16     4.6755        4.7043  (  0.61%)
 17     4.8877        4.8579  (  0.61%)
 18     4.9951        5.0071  (  0.24%)
 19     5.1312        5.1522  (  0.41%)
 20     5.2699        5.2936  (  0.45%)

D

Translation of: Perl 6

<lang d>import std.stdio, std.random, std.math, std.algorithm, std.range;

real analytical(in int n) /*pure nothrow*/ {

   real total = 0.0;
   foreach (immutable k; 1 .. n + 1) {
       immutable x = reduce!q{a * b}(1.0L, iota(n - k + 1, n + 1))
                     * k ^^ 2;
       total += x / ((cast(real)n) ^^ (k + 1));
   }
   return total;

}

int[] randomMapping(in int size) {

   static int[1000] result;
   foreach (ref r; result[0 .. size])
       r = uniform(1, size + 1);
   return result[0 .. size];

}

size_t loopLength(in int[] mapping, in int size) {

   static bool[1000] seen;
   seen[0 .. size + 1] = false;
   int current = 1;
   size_t steps = 0;
   while (!seen[current]) {
       seen[current] = true;
       current = mapping[current - 1];
       steps++;
   }
   return steps;

}

void main() {

   enum maxN  = 20;
   enum nTrials = 200_000;
   writeln(" n    average    analytical     (error)");
   writeln("===  =========  ============  ==========");

   foreach (immutable n; 1 .. maxN + 1) {
       long total = 0;
       foreach (_; 0 .. nTrials)
           total += loopLength(randomMapping(n), n);
       immutable average = total / cast(real)nTrials;
       immutable an = analytical(n);
       immutable percentError = abs(an - average) / an * 100;
       immutable errorS = format("%2.4f", percentError);
       writefln("%3d  %9.5f  %12.5f  (%7s%%)",
                n, average, an, errorS);
   }

}</lang>

Output:

 n    average    analytical     (error)
===  =========  ============  ==========
  1    1.00000       1.00000  ( 0.0000%)
  2    1.50314       1.50000  ( 0.2093%)
  3    1.88832       1.88889  ( 0.0303%)
  4    2.21606       2.21875  ( 0.1210%)
  5    2.51379       2.51040  ( 0.1352%)
  6    2.77649       2.77469  ( 0.0646%)
  7    3.01115       3.01814  ( 0.2314%)
  8    3.24209       3.24502  ( 0.0902%)
  9    3.45700       3.45832  ( 0.0379%)
 10    3.65898       3.66022  ( 0.0337%)
 11    3.85375       3.85237  ( 0.0357%)
 12    4.03616       4.03607  ( 0.0021%)
 13    4.20220       4.21235  ( 0.2409%)
 14    4.37912       4.38203  ( 0.0665%)
 15    4.53510       4.54581  ( 0.2354%)
 16    4.70602       4.70426  ( 0.0374%)
 17    4.86300       4.85787  ( 0.1056%)
 18    5.00708       5.00706  ( 0.0003%)
 19    5.14865       5.15220  ( 0.0688%)
 20    5.29396       5.29358  ( 0.0069%)

With nTrials = 10_000_000:

 n    average    analytical     (error)
===  =========  ============  ==========
  1    1.00000       1.00000  ( 0.0000%)
  2    1.50011       1.50000  ( 0.0074%)
  3    1.88835       1.88889  ( 0.0286%)
  4    2.21945       2.21875  ( 0.0317%)
  5    2.51045       2.51040  ( 0.0018%)
  6    2.77477       2.77469  ( 0.0029%)
  7    3.01850       3.01814  ( 0.0120%)
  8    3.24473       3.24502  ( 0.0089%)
  9    3.45771       3.45832  ( 0.0175%)
 10    3.65986       3.66022  ( 0.0096%)
 11    3.85196       3.85237  ( 0.0107%)
 12    4.03585       4.03607  ( 0.0055%)
 13    4.21336       4.21235  ( 0.0239%)
 14    4.38263       4.38203  ( 0.0137%)
 15    4.54628       4.54581  ( 0.0103%)
 16    4.70436       4.70426  ( 0.0021%)
 17    4.85825       4.85787  ( 0.0078%)
 18    5.00768       5.00706  ( 0.0123%)
 19    5.15152       5.15220  ( 0.0132%)
 20    5.29326       5.29358  ( 0.0061%)

Mathematica

<lang mathematica>Grid@Prepend[

 Table[{n, #1, #2, 
     Row[{Round[10000 Abs[#1 - #2]/#2]/100., "%"}]} &@
   N[{Mean[Array[
       Length@NestWhileList[#, 1, UnsameQ[##] &, All] - 1 &[# /. 
           MapIndexed[#21 -> #1 &, 
            RandomInteger[{1, n}, n]] &] &, 10000]], 
     Sum[n! n^(n - k - 1)/(n - k)!, {k, n}]/n^(n - 1)}, 5], {n, 1, 
   20}], {"N", "average", "analytical", "error"}]</lang>

Output:

N	average	analytical	error
1	1.0000	1.0000		0.%
2	1.5017	1.5000		0.11%
3	1.8910	1.8889		0.11%
4	2.2334	2.2188		0.66%
5	2.5090	2.5104		0.06%
6	2.8092	2.7747		1.24%
7	3.0468	3.0181		0.95%
8	3.2253	3.2450		0.61%
9	3.4695	3.4583		0.32%
10	3.6661	3.6602		0.16%
11	3.8662	3.8524		0.36%
12	4.0393	4.0361		0.08%
13	4.2232	4.2123		0.26%
14	4.3496	4.3820		0.74%
15	4.5706	4.5458		0.55%
16	4.6963	4.7043		0.17%
17	4.8548	4.8579		0.06%
18	5.0671	5.0071		1.2%
19	5.1702	5.1522		0.35%
20	5.2264	5.2936		1.27%

Perl 6

Runs on Rakudo Warszawa (2012.12).

<lang perl6>constant MAX_N = 20; constant TRIALS = 100;

for 1 .. MAX_N -> $N {

   my @lengths = loop-length(random-mapping($N)) xx TRIALS;
   my $average = ([+] @lengths) / @lengths;
   my $analytical = analytical($N);
   my $percent_error = abs($analytical - $average) / $analytical * 100;

   FIRST say " N    average    analytical    (error)";
   FIRST say "===  =========  ============  =========";
   
   printf "%3d  %9.4f  %12.4f    (%4.2f%%)\n",
       $N, $average, $analytical, $percent_error ;    

}

sub random-mapping($size) {

   return hash .list Z=> .roll($size) given ^$size;

}

sub loop-length(%mapping) {

   my ($steps, %seen);
   loop (
       my $current = 0;
       !%seen{$current}++;
       $current = %mapping{$current}
   ) { $steps++ }
   return $steps;

}

sub analytical($N) {

   [+] (1..$N).map: -> $k { $N ** ($k + 1) R/ [*] $k**2, $N - $k + 1 .. $N }

}</lang>

Example:

$ perl6 loop-lengths
 N    average    analytical    (error)
===  =========  ============  =========
  1     1.0000        1.0000  (  0.00%)
  2     1.4992        1.5000  (  0.05%)
  3     1.8784        1.8889  (  0.56%)
  4     2.2316        2.2188  (  0.58%)
  5     2.4982        2.5104  (  0.49%)
  6     2.7897        2.7747  (  0.54%)
  7     3.0153        3.0181  (  0.09%)
  8     3.2429        3.2450  (  0.07%)
  9     3.4536        3.4583  (  0.14%)
 10     3.6649        3.6602  (  0.13%)
 11     3.8091        3.8524  (  1.12%)
 12     3.9986        4.0361  (  0.93%)
 13     4.2074        4.2123  (  0.12%)
 14     4.3711        4.3820  (  0.25%)
 15     4.5275        4.5458  (  0.40%)
 16     4.6755        4.7043  (  0.61%)
 17     4.8877        4.8579  (  0.61%)
 18     4.9951        5.0071  (  0.24%)
 19     5.1312        5.1522  (  0.41%)
 20     5.2699        5.2936  (  0.45%)