# Stopping time of a Markov chain

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

-
I am not an expert, but wanted to point out that there is a 'standard' technique for approximating Markov chains by ODE's. One important name is Kurtz's theorem. The survey article "Differential equation approximations for Markov chains " by Richard W.R. Darling and James Ritchie Norris in Probability Surveys gives a good introduction, with a few examples about how to account for exit time approximations. One difficulty is that your increments are in theory quite large, even after rescaling. Truncating the step sizes at e.g. $\sqrt{n \log(n)}$ could resolve this problem. –  QAMS Dec 13 '11 at 3:55
Empirically, for N large, it looks like the probability distribution of A(t) for every t is a beta distribution. Not sure if it helps. –  Arthur B Dec 13 '11 at 15:06
@QAMS I am sure I am understanding the truncation. Similar problems were answered by splitting the process into stages and estimating the number of rounds required to get the process to the next stage. My understanding is that differential equation approximations are mostly employed for showing almost sure exit not investigating the exit time. I also thought at first that it could help but as you said increments are large. –  folmez Dec 14 '11 at 16:54
correction in above comment: "I am \emph{not} sure ... " –  folmez Dec 14 '11 at 17:06

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

-
Phase 2 can be proved to require a constant number of rounds the way you suggested. I think a Chernoff bound also works. Thanks for your note for phase 1, I am definitely going to try that. [Chat mode on] my advisor Janet Best and post-doc Deena Schmidt said "Hi!" [Chat mode off] –  folmez Dec 19 '11 at 17:04

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!

-
It actually is. I have read his paper and an earlier Frieze-Grimmet paper on the same problem. Dr. Pittel isn't as active as before though. It's hard to find him in his office. –  folmez Jan 21 '12 at 17:00

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.

-