5
$\begingroup$

Let $A_0$ be a list of $ n$ distinct elements. By sampling with replacement the elements of $A_0$, we obtain a new list $A_1$ of $n$ elements that are not necessarily distinct. Repeat the same process on $A_1$ we obtain $A_2$ and so on. After $ T_n$ steps we first obtain a list of same elements. What do we know about the law of $ T_n$, notably when $n \rightarrow \infty$?

Here is the empirical distribution of $T_{10}$ from $50000$ samples.

empirical_law

$\endgroup$
3
  • 2
    $\begingroup$ It should be easy enough to answer the question for $n=2$, $n=3$, maybe even $n=4$. Maybe a pattern shows up. $\endgroup$ Commented Apr 21, 2022 at 3:20
  • $\begingroup$ @GerryMyerson What exactly do you mean by "answer the question for $n=2$"? $\endgroup$ Commented Apr 22, 2022 at 19:22
  • $\begingroup$ @math, the question begins, "Let $A_0$ be a list of $n$ distinct elements," and then goes on to give some empirical results for $n=10$. I'm suggesting that for smaller values of $n$ it should be possible to work out the exact distribution of $T_n$, and possibly get some idea of what $T_n$ looks like in general. $\endgroup$ Commented Apr 22, 2022 at 22:57

2 Answers 2

4
$\begingroup$

The model that you are describing is known in the literature as the "Wright-Fisher" model. It represents the genealogy of a population with fixed size $n$, where generation $k+1$ is made of $n$ individuals whose parent is uniformly sampled from generation $k$ (independently for different individuals).

Here your list $A_k$ describes the $k$-th generation by recording the individuals alive at time $0$ they each descend from. Interpreted this way, your question then becomes: after how many generations do all the individuals in the population descend from the same ancestor at time 0 ?

This is exactly the kind of result that people have asked about that model so a lot is known. In particular we have the following convergence in distribution towards a random variable:

$$ \frac{T_n}{n} \underset{n\rightarrow \infty}{\rightarrow} \tau, $$

where $\tau$ is the (random) time that it takes for a Kingman's coalescent to reach $1$. The random time $\tau$ can be expressed as

$$ \tau=\sum_{i=2}^\infty E_i $$

where $(E_i)_{i\geq 2}$ is a family of independent exponentially distributed random variables where $E_i \sim \mathrm{Exp}\left(\binom{i}{2}\right)$.

I don't know exactly what the standard reference for this fact should be, but the main idea is to invert the arrow of time: start with the population at time $t$ and consider how many parents at time $t-1$ they stem from, then $t-2$, $t-3$ etc. This forms a non-increasing process for which you can do explicit computations. This seems to be the historical reference where this idea appears.

$\endgroup$
3
$\begingroup$

One can show the bounds $n \leq \mathbb{E}[T_n] \leq n(n-1)$, and that the law of $T_n$ asymptotically decays exponentially at rate $\lim\limits_{t \to \infty} -\frac{\log\mathbb{P}(T_n > t)}{t} = -\log\left(1 - \frac{1}{n}\right) ( \approx \frac{1}{n}$ for large $n$) via a martingale argument.

Let $p^{k}_{t}$ be the frequency of the $k^{\text{th}}$ element after $t$ iterations, and define $q_t := (p^{1}_t, p^{2}_t, \ldots, p^{n}_t)$. Let $\mathcal{F_t}$ be the sigma algebra generated by $\{q_s\}_{s \leq t}$. By the definition of the resampling process, we have: $$ q_{t+1} \sim \frac{1}{n} \cdot \text{Multi}(n, q_t) $$ and initial condition $$ q_0 = \left(\frac{1}{n}, \frac{1}{n}, \ldots, \frac{1}{n}\right) $$

We may now calculate: $$ \mathbb{E}[(p^{k}_{t+1})^2 | \mathcal{F}_{t}] = \text{Var}(p^{k}_{t+1} | \mathcal{F}_{t}) + \mathbb{E}[p^{k}_{t+1} | \mathcal{F}_{t}]^2 \\ = \frac{1}{n^2} \left( n p^k_t (1 - p^k_t) + (n p^k_t)^2 \right) = \left(1 - \frac{1}{n}\right)(p^k_t)^2 + \frac{1}{n}p^k_t $$ where we used the first two moments of the multinomial distribution that are given e.g. here.

Summing over all $k$, this becomes: $$ \mathbb{E}[||q_{t+1}||^2 | \mathcal{F}_{t}] = \left(1 - \frac{1}{n}\right)||q_t||^2 + \frac{1}{n} $$

Defining $X_t := \left(1 - \frac{1}{n}\right)^{-(t+1)} \cdot \left(1 - ||q_t||^2 \right)$, we can rewrite this as: $$ \mathbb{E}[X_{t+1} | \mathcal{F}_{t}] = X_t $$

Hence, $X_t$ is a martingale with respect to the filtration $\{\mathcal{F}_{t}\}_{t \in \mathbb{N}}$.

Now, note that $||q_t||^2 = \sum_k (p^{k}_t)^2 \leq \sum_k p^{k}_t = 1$ with equality only when $q_t$ is supported on only 1 element. This corresponds to the desired termination condition. Thus, $T_n$ can be characterized as the stopping time $T_n = \min \{t \in \mathbb{N} | X_t = 0\}$.

Define the additional stopping time $\tau := \min(T_n, t)$. As $\tau$ is bounded, we may apply the optional stopping theorem to $X$ and $\tau$ to obtain: $$ 1 = \mathbb{E}[X_0] = \mathbb{E}[X_{\tau}] = 0 \cdot \mathbb{P}(T_n \leq t) + \left(1 - \frac{1}{n}\right)^{-(t+1)} \cdot \mathbb{E}\left[ \left(1 - ||q_t||^2 \right) \bigg| T_n > t \right] \cdot \mathbb{P}(T_n > t) $$

Note that we have the upper bound: $$\mathbb{E}\left[ \left(1 - ||q_t||^2 \right) \bigg| T_n > t \right] \leq 1 - \frac{1}{n}$$ which follows from Jensen's inequality, as $\frac{1}{n} \sum (p^{k}_t)^2 \geq \left( \frac{\sum_k p^{k}_t}{n}\right)^2 = \frac{1}{n^2}$. Rearranging gives the desired bound.

We also have the lower bound: $$\mathbb{E}\left[ \left(1 - ||q_t||^2 \right) \bigg| T_n > t \right] \geq \frac{1}{n}$$ This follows from the following considerations. Note that $T_n > t$ implies that $||q_t|| \neq 1$, and hence $p^{k}_t < 1$ for all $k$. As the $p^{k}_t$ are normalized frequencies of $n$ items, this further implies that $p^{k}_t \leq \frac{n-1}{n}$, and hence $(p^{k}_t)^2 \leq \frac{n-1}{n} p^{k}_t$. Summing over $k$ and rearranging gives us $1 - ||q_t||^2 \geq \frac{1}{n}$, as desired.

Substituting these two bounds gives: $$\left(1 - \frac{1}{n}\right)^{t}\leq \mathbb{P}(T_n > t) \leq n \left(1 - \frac{1}{n}\right)^{t+1} $$

Taking logs, dividing by t, and taking a limit gives the desired rate of decay $\lim\limits_{t \to \infty} -\frac{\log\mathbb{P}(T_n > t)}{t} = -\log\left(1 - \frac{1}{n}\right)$.

Summing over all $t \geq 0$ and using the identity $\mathbb{E}[Y] = \sum_{t \geq 0} \mathbb{P}(Y > t)$ gives: $$ n \leq \mathbb{E}[T_n] \leq n(n-1)$$ as desired.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .