MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited body

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

1

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