Project Euler Problem 819
Given an n-tuple of numbers another n-tuple is created where each element of the new n-tuple is chosen randomly from the
Solution
Answer: 1995.975556
Let $N=n$.
Interpret the process backwards in time:
- At each step, every position in the new tuple chooses one position from the previous tuple uniformly at random.
- Tracing ancestry backward, if there are currently $k$ distinct ancestral lineages, then each lineage independently chooses one of the $N$ parents.
- The next number of lineages is therefore the number of occupied boxes when throwing $k$ balls into $N$ boxes.
Hence the transition probability is
$$P(k\to j)=\frac{S(k,j),(N)_j}{N^k},$$
where:
- $S(k,j)$ is a Stirling number of the second kind,
- $(N)_j=N(N-1)\cdots(N-j+1)$.
Let $E_k$ be the expected remaining time to absorption (all equal) starting from $k$ lineages. Then
$$E_1=0,$$
and for $k\ge2$,
$$E_k = \frac{ 1+\sum_{j=1}^{k-1} P(k\to j),E_j }{ 1-P(k\to k) }.$$
We need $E_N$ for $N=1000$.
A numerically stable dynamic program computes the occupancy probabilities row-by-row using
$$P_k(j) = P_{k-1}(j-1)\frac{N-j+1}{N} + P_{k-1}(j)\frac{j}{N}.$$
Using this recurrence gives
$$E(1000)=1995.9755563020154999\ldots$$
Rounded to 6 digits after the decimal place:
Answer: 1995.975556