Problem Statement

Let f be a uniformly-randomly chosen mapping from the numbers 1..N to the numbers 1..N (note: not necessarily a permutation of 1..N; the mapping could produce a number in more than one way or not at all). 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:

Let's start with the solution:

function average(n, reps)
  local count = 0
  for r = 1, reps do
    local f = {}
    for i = 1, n do f[i] = math.random(n) end
    local seen, x = {}, 1
    while not seen[x] do
      seen[x], x, count = true, f[x], count+1
    end
  end
  return count / reps
end

function analytical(n)
  local s, t = 1, 1
  for i = n-1, 1, -1 do t=t*i/n s=s+t end
  return s
end

print(" N    average    analytical    (error)")
print("===  =========  ============  =========")
for n = 1, 20 do
  local avg, ana = average(n, 1e6), analytical(n)
  local err = (avg-ana) / ana * 100
  print(string.format("%3d  %9.4f  %12.4f  (%6.3f%%)", n, avg, ana, err))
end