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.

Improve this question
$\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$
    – Douglas Zare
    Commented 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
    Commented 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$
    – Douglas Zare
    Commented 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$
    – Douglas Zare
    Commented Mar 28, 2014 at 2:35

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented 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$
    – Douglas Zare
    Commented Mar 30, 2014 at 1:10

You must log in to answer this question.

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