Consider a sequence of the the following stochastic process. Let $b_0=1$, and let $n >1$. At each step $t$, let $b_t \sim Bin(n,\frac{b_{t-1}}{n})$. The process stops when either $b_t=0$ $b_t=n$. This is a martingale.

Question: What is the rate of convergence of this series? Specifically, I am interested in lower-bounding the probability that after $t=O(\log n)$(i.e., for some $t'\leq t$, $b_{t'}=0$. More generally, I'm interested in obtaining such lower bounds as a function of $t$.

I suspect that something like this may have been studied, but I'm not sure where to look.

  • $\begingroup$ It's a martingale starting at $1$ and ending at $0$ or $n$, so as $t\to \infty$ it ends at $0$ with probability $(n-1)/n$, never $1-o(1)$. Did you mean to ask something else? $\endgroup$ – Douglas Zare Mar 27 '14 at 23:26
  • $\begingroup$ Right. $o(1)$ was supposed to be $o_n(1)$; i.e., it approaches $1$ as $n$ grows. For starters, I want to know how fast it converges to $1-1/n$. In particular, what is the probability of stopping with $b_t=0$ for $t =O(\log n)$? $\endgroup$ – JoelO Mar 27 '14 at 23:54
  • $\begingroup$ This appears to model neutral genetic drift. I looked that up and found that for $n$ even, this is called the Wright-Fisher model, and found this question: math.stackexchange.com/questions/585578/… $\endgroup$ – Douglas Zare Mar 28 '14 at 2:34
  • $\begingroup$ I'd expect that the probability will go to $1$ as long as $t$ goes to infinity with $n$. $\endgroup$ – Douglas Zare Mar 28 '14 at 2:35

This model is called the Wright-Fisher model for genetic drift (when $n$ is even). Each gene in a population is a copy of a random gene from the previous generation. You are looking at the case that a mutation occurs at time $0$, and then you are asking how long it takes for the gene to be fixed. The following argument seems to be standard:

Let $D_t$ be the count of pairs of genes of different types. $D_t = b_t(n-b_t)$. So, this starts at $n-1$, it is always at most $n^2/4$, and it is $0$ when the gene is fixed.

$$\begin{eqnarray}E[D_{t+1}|b_t] &=& {n \choose 2}\times 2\frac{b_t}{n}\frac{n-b_t}{n} \newline &=& \frac{n^2-n}{n^2} b_t(n-b_t) \newline &=&(1-\frac{1}{n})D_t\end{eqnarray}$$

Since $D_0 = n-1, E[D_t] = (n-1)(1-\frac{1}{n})^t.$

We can use this for easy upper and lower bounds on the probability that the population has been fixed. or equivalently that it has not been fixed. Let $\tau$ be the first time the population is fixed. If $\tau \le t$ then $D_t=0$. If $\tau \gt t$ then $n-1 \le D_t \le n^2/4$.

$$\begin{eqnarray}P(\tau \gt t) (n-1) &\le & ~~~~E[D_t] &\le & P(\tau \gt t) \frac{n^2}{4} \newline \bigg(1-\frac{1}{n}\bigg)^{-t}&\le & P(\tau > t)^{-1} &\le & \frac{n^2}{4(n-1)} \bigg(1-\frac{1}{n}\bigg)^{-t} \newline \bigg(1-\frac{1}{n}\bigg)^t& \ge& P(\tau > t) &\ge & \frac{4(n-1)}{n^2} \bigg(1-\frac{1}{n}\bigg)^t.\end{eqnarray}$$

You ask about the probability that the gene is fixed in one direction. The probability that the mutation takes over the population is $1/n$, so a lower bound for the probability that $b_t = 0$ is $1-(1-\frac{1}{n})^t-1/n$.

While the estimate

$\frac{D_0}{n-1}\bigg(1-\frac{1}{n}\bigg)^t \ge P(\tau \gt t) \ge \frac{4D_0}{n^2} \bigg(1-\frac{1}{n}\bigg)^t$

is reasonable when $b_0 = \Theta(n)$, it's not great if you fix $b_0=1$ as $n\to \infty$. $\bigg( 1-\frac{1}{n} \bigg) ^t \approx e^{-t/n}$. This estimate gets weaker, but the chance that $b_t=0$ increases with $n$. In the limit $n\to \infty$ we can consider the map $b_{t+1} = \textrm{Pois}(b_t)$. As $t\to \infty, P(b_t=0) \to 1$. This can be computed exactly:

$$\begin{eqnarray}P(b_1 = 0) &=& e^{-1} \newline P(b_2 = 0) &=& e^{e^{-1}-1} \newline P(b_3 = 0) &=& e^{e^{e^{-1}-1}-1} \newline P(b_{t+1} = 0) &=& \sum_{k=0}^\infty \frac{1}{e~ k!}P(b_t=0)^k = \exp(P(b_t=0)-1)\end{eqnarray}$$

$e^{x-1}$ has a parabolic fixed point at $1$, with expansion $1 + (x-1) + \frac{1}{2}(x-1)^2 + o((x-1)^2)$. This indicates that the convergence to $1$ is something like $1-c/t$. Since $P(b_{1000} = 0) = 0.998008$ it appears that $c = 2$.

  • $\begingroup$ Just a quick followup question: The lower bound seems a bit insufficient for what I need. So alternatively, can we give a concentration bound on $b_i$? In particular, can we reasonably upper-bound the probability that $b_i$ is larger than some function of $n$, for any $i$? From what I understand from the Wikipedia entry, the variance of $b_i$ is given by: $Var[b_i/n] \approx \frac{b_i (n-b_i)}{n^2}(1-e^{-t/2n}) < b_i/n$, right? If that's true, we can just apply, say, Chebyshev's inequality for that purpose, right? $\endgroup$ – JoelO Mar 30 '14 at 0:41
  • 1
    $\begingroup$ @JoelO: Yes, I'm working on an edit. Variance bounds give you better results when $b_0$ is $o(n)$. The probability that $b_t$ is large can't be too high because it is a martingale and the average stays the same. $\endgroup$ – Douglas Zare Mar 30 '14 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.