1
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Mar 27, 2014 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, 2014 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$ Mar 28, 2014 at 2:34
  • $\begingroup$ I'd expect that the probability will go to $1$ as long as $t$ goes to infinity with $n$. $\endgroup$ Mar 28, 2014 at 2:35

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
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, 2014 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$ Mar 30, 2014 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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