Problem 819

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, \dots, 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.

迭代抽样

给定一个 $n$ 元数组，考虑从中随机抽样得到的新 $n$ 元数组。例如，当原数组是 $(2, 2, 3)$ 时，新数组的第一位有 $2 / 3$ 的概率是 $2$ ，有 $8 / 27$ 的概率全都是 $2$ ，有 $4 / 9$ 的概率获得原数组（不计顺序）。

从数组 $(1, 2, \dots, n)$ 出发，不断随机抽样直至数组中所有的数都相同，记所需要的步数的期望为 $E (n)$ 。

已知 $E (3) = 27 / 7$ ， $E (5) = 468125 / 60701 \approx 7.711982$ ，保留小数点后 $6$ 位。

求 $E (10^{3})$ ，并将你的答案保留小数点后 $6$ 位。