¿Qué ocurre con un paseo aleatorio cuando aumentamos las probabilidades de salir bien?

Question

Consideremos un paseo aleatorio sobre los enteros en el que la probabilidad de pasar de $n$ a $n+1$ es $p_n$ (y por supuesto, la probabilidad de pasar de $n$ a $n-1$ es $1-p_n$ ); suponemos que todos los $p_n$ son estrictamente menores que $1$ . Supongamos que sabemos que este paseo aleatorio está bastante bien concentrado; por ejemplo, supongamos que sabemos que $$P(|X(t) - (1/3)t| \geq c \sqrt{t}) \leq e^{-c^2}$$ donde $X(t)$ es el estado del paseo después de $t$ pasos.

Ahora supongamos que aumentamos cada $p_n$ por $\epsilon$ (y, en consecuencia, disminuye la probabilidad de pasar de $n$ a $n-1$ por $\epsilon$ ), donde $\epsilon$ es un número tal que $p_n + \epsilon < 1$ para todos $n$ . Sea $Y(t)$ sea el estado de la nueva cadena después de $t$ pasos. Mi pregunta es: ¿se mantiene un resultado de concentración similar para $Y(t)$ ?

Parece muy intuitivo que $Y(t)$ debe concentrarse en torno a $(1/3)t + 2 \epsilon t$ .

Answer 1

Escribe $Z(t) = Y(t) - X(t)$ . Entonces \[ Y(t)-(1/3 + 2 \epsilon )t = \Big (X(t) - (1/3)t \Big ) + \Big (E[Z(t)]-2 \epsilon t \Big ) + \Big (Z(t) - E[Z(t)] \Big ). \] La concentración del primer término viene dada por su suposición. Para el tercer término, $Z(t)$ es la suma de $t$ variables aleatorias acotadas iid, por lo que $P(|Z(t) -E[Z(t)] | \ge x \sqrt{t} ) \le 2 e^{-C x^2}$ para alguna constante $C>0$ por la desigualdad de Hoeffding; esto resuelve el tercer término anterior.

Para el medio plazo, $E[Z(t)]-2\epsilon t=0$ al notar que $Z(t)-2\epsilon t$ es una Martingala con media cero en el tiempo 0.

Por el límite de la unión, con probabilidad al menos $1-2e^{-C x^2} - e^{-c^2}$ obtenemos \[ |Y(t)-(1/3 + 2 \epsilon )t| \le (c+x) \sqrt t. \]

Answer 2

NOTA : Esto es totalmente erróneo - ver comentarios.

Dejemos que $E(t)$ sea el paseo aleatorio unidireccional que añade uno a su estado actual con probabilidad $\epsilon$ y permanece en su estado actual con probabilidad $1-\epsilon$ . ¿No es cierto que $Y(t) = X(t) + E(t)$ ¿Exactamente? - es decir, las distribuciones de las variables aleatorias $Y(t)$ y $X(t) + E(t)$ son exactamente iguales?

Suponiendo que tengo razón en que son lo mismo, entonces un resultado de concentración para $Y$ se desprende del resultado de la concentración hipotética para $X$ y la concentración estándar que se puede calcular para $E(t)$ : si $Y(t) - (\frac13+\epsilon)t$ supera $c\sqrt t$ , entonces uno de $X(t) - \frac13t$ o $E(t) - \epsilon t$ debe superar $\frac c2\sqrt t$ .