Stopping time of a Markov chain

Question

Let $A(t+1)=A(t)+Bin(n-A(t),\frac{A(t)}{n})$ with $A(0)=1$ and let $T_n$ be the minimum of $t$ such that $A(t)=n$.

I think that $A(t)$ should behave like the naive deterministic approximation $a(t+1)=a(t)+(n-a(t))\frac{a(t)}{n}$ with $a(0)=1$. It can be shown that $t$ needs to be greater than $\log_2{n}+f(\alpha)$ in order to obtain $a(t)\geq \alpha n$. Here $f$ does not depend on $n$.

Is it then true that $$\mathbb{P}(|T_n-\log_2{n}|>\omega(n))\to 0$$ for any $\omega(n)\to \infty$, however slowly?

I am trying to prove this in three phases: from $A(0)=1$ to $A(S_1)=bn$, then from $bn$ to $cn$ in $S_2$ stages and from $cn$ to $n$ in $S_3$ stages for $0 < b < c <1$.

Answer 1

I think your approach is generally correct. I will note that for your first phase, so long as $A(t) < \epsilon n$, the process $A(t)$ is well approximated by a branching process where the offspring distribution is 1 + Poisson (1). Since this has mean equal to 2 and cannot get extinct, the Kesten-Stigum theorem says that at time $t$, $A(t)$ really is of order $W 2^t$ for some random variable $W>0$. You see indeed that it thus takes $t =\log_2 n $ to make this equal to $n$, so phase 1 takes $\log_2 n $ + a random variable whose tail probabilities are uniformly bounded in $n$, as needed.

In phase 2, you can either use the ODE approach with Ethier-Kurtz type of arguments, as suggested by QAMS, or simply note the following. The probability that a Binomial $(N,p)$ deviates from its mean $Np$ (say, is less than $Np/2$) is exponential in $Np$. This means that, over a logarithmic number of trials, the probability you would observe one such deviations tends to 0. Hence during phase 2, you know that each step you add at least a $(N-A(t))\epsilon/2$ individuals, which shows that phase 2 indeed only takes a constant number of steps with overwhelming probability.

Phase 3 is a bit more delicate (you want to avoid a coupon-collector effect where collecting the last individual takes more time than it should), but I think this sort of reasoning should help you get started...

Answer 2

I suppose you know that this process you're looking at is very similar to the one treated in Boris Pittel's paper "On Spreading a Rumor" (SIAM Journal on Applied Mathematics, Vol. 47, No. 1, Feb., 1987). In your notation, I believe his process would be written $$ A(t+1) \sim A(t) + Bin(n-A(t),1-(1-1/n)^{A(t)}).$$ So I would recommend knocking on his door and seeing what he suggests!

Answer 3

I think I did manage to get something useful in five phases. With high probability,

1) $A=1$ to $A\in(\frac{n}{6},\frac{2n}{3})$ in $\log_2{n}\pm 1$ rounds,

2) $A=an$ to $A=dn$ for some $0< d <<1$ in $O(1)$ rounds,

3) From $dn$ to $n-n^\alpha$ for some $\frac{1}{2}<\alpha<1$ in $O(\log_2{\log{n}})$ rounds,

4) From $n-n^\alpha$ to $n-n^{\beta}$ for fome $\beta < \frac{1}{2}$ in $O(1)$ rounds,

5) From $n-n^{\beta}$ to $n$ in one round.

So $\frac{T_n}{\log_2{n}} \to 1$ in probability, which is good enough for me.