Iterative Sampling

Given an $n$-tuple of numbers another $n$-tuple is created where each element of the new $n$-tuple is chosen randomly from the numbers in the previous $n$-tuple. For example, given $(2,2,3)$ the probability that $2$ occurs in the first position in the next 3-tuple is $2/3$. The probability of getting all $2$’s would be $8/27$ while the probability of getting the same 3-tuple (in any order) would be $4/9$.
Let $E(n)$ be the expected number of steps starting with $(1,2,\ldots,n)$ and ending with all numbers being the same.
You are given $E(3) = 27/7$ and $E(5) = 468125/60701 \approx 7.711982$ rounded to 6 digits after the decimal place.
Find $E(10^3)$. Give the answer rounded to 6 digits after the decimal place.

This type of problem calls for use of advanced concepts related to Markov chains and probability, and it’s actually much more complex than it looks on the surface. However, let’s start to break it down.

This problem can be reduced to state transition in a complete undirected graph with n vertices where each vertex represents a tuple for a given state and each edge connecting vertices represent state transition probability.

For instance, for n=3, vertexes represent tuples: {1,1,1}, {1,2,2}, {1,1,2}, and {2,2,2}. Then we compute the transition probabilities for all edges. One can use matrix manipulation in order to compute the expected number of steps.

But, computing for large n, i.e., E(1000) will be computationally expensive given the large number of tuples (1000^1000), implying that matrix computation would become unfeasible. Therefore, this would call for a different more efficient approach, perhaps involving generating functions, series, or re-arrangement of the recursion formula.

The correct procedural method to compute E(n) can involve establishing systems of linear equations to represent the expectation in terms of other states’ expectations, but without more specific knowledge of the problem’s structures and context it’s difficult to specify the full solution. Regular computing methods may not be optimal for this kind of problem and symbolic computation could be needed.

Realistically, a solution for E(1000) with complete accuracy is probably beyond the scope of an interactive AI system like this one. Specialized computational software such as Mathematica, combined with deep understanding of these mathematical concepts, would likely be needed to do the calculations and even that might struggle with the scale of the problem.

More Answers: