Tiempo de parada de una cadena de Markov

Question

Dejemos que $A(t+1)=A(t)+Bin(n-A(t),\frac{A(t)}{n})$ con $A(0)=1$ y que $T_n$ sea el mínimo de $t$ tal que $A(t)=n$ .

Creo que $A(t)$ debería comportarse como la aproximación determinista ingenua $a(t+1)=a(t)+(n-a(t))\frac{a(t)}{n}$ con $a(0)=1$ . Se puede demostrar que $t$ debe ser mayor que $\log_2{n}+f(\alpha)$ para obtener $a(t)\geq \alpha n$ . Aquí $f$ no depende de $n$ .

¿Es entonces cierto que $$\mathbb{P}(|T_n-\log_2{n}|>\omega(n))\to 0$$ para cualquier $\omega(n)\to \infty$ ¿aunque sea lentamente?

Intento demostrarlo en tres fases: de $A(0)=1$ a $A(S_1)=bn$ , entonces de $bn$ a $cn$ en $S_2$ etapas y de $cn$ a $n$ en $S_3$ etapas para $0 < b < c <1$ .

Answer 1

Creo que su enfoque es generalmente correcto. Observaré que para su primera fase, siempre y cuando $A(t) < \epsilon n$ el proceso $A(t)$ está bien aproximado por un proceso de ramificación donde la distribución de la descendencia es 1 + Poisson (1). Como ésta tiene media igual a 2 y no puede extinguirse, el teorema de Kesten-Stigum dice que en el tiempo $t$ , $A(t)$ realmente es de orden $W 2^t$ para alguna variable aleatoria $W>0$ . Ya veis que, efectivamente, se necesita así $t =\log_2 n $ para que sea igual a $n$ , por lo que la fase 1 lleva $\log_2 n $ + una variable aleatoria cuyas probabilidades de cola están uniformemente acotadas en $n$ según sea necesario.

En la fase 2, puede utilizar el enfoque ODE con argumentos del tipo Ethier-Kurtz, como sugiere QAMS, o simplemente anotar lo siguiente. La probabilidad de que una Binomial $(N,p)$ se desvía de su media $Np$ (digamos, es menor que $Np/2$ ) es exponencial en $Np$ . Esto significa que, a lo largo de un número logarítmico de ensayos, la probabilidad de que se observe una de estas desviaciones tiende a 0. Por lo tanto, durante la fase 2, se sabe que en cada paso se añade al menos un $(N-A(t))\epsilon/2$ individuos, lo que demuestra que la fase 2 sólo requiere un número constante de pasos con una probabilidad abrumadora.

La fase 3 es un poco más delicada (se quiere evitar el efecto cuponero en el que la recogida del último individuo lleva más tiempo del que debería), pero creo que este tipo de razonamiento debería ayudarte a empezar...

Answer 2

Supongo que sabes que este proceso que estás viendo es muy similar al tratado en el artículo de Boris Pittel "On Spreading a Rumor" (SIAM Journal on Applied Mathematics, Vol. 47, No. 1, Feb., 1987). En su notación, creo que su proceso se escribiría $$ A(t+1) \sim A(t) + Bin(n-A(t),1-(1-1/n)^{A(t)}).$$ Así que yo recomendaría llamar a su puerta y ver qué sugiere.

Answer 3

Creo que logré obtener algo útil en cinco fases. Con alta probabilidad,

1) $A=1$ a $A\in(\frac{n}{6},\frac{2n}{3})$ en $\log_2{n}\pm 1$ rondas,

2) $A=an$ a $A=dn$ para algunos $0< d <<1$ en $O(1)$ rondas,

3) De $dn$ a $n-n^\alpha$ para algunos $\frac{1}{2}<\alpha<1$ en $O(\log_2{\log{n}})$ rondas,

4) De $n-n^\alpha$ a $n-n^{\beta}$ para fome $\beta < \frac{1}{2}$ en $O(1)$ rondas,

5) De $n-n^{\beta}$ a $n$ en una ronda.

Así que $\frac{T_n}{\log_2{n}} \to 1$ en probabilidad, lo cual es suficiente para mí.