La mezcla de dos diferentes sesgada monedas

Question

Mi problema es el siguiente:

Tengo dos sesgada de las monedas con las probabilidades de $p_1$ $p_2$ de aterrizaje de cabezas. Voy a empezar con monedas de 1 y mezcle hasta que se cae de cabeza. Entonces me swap de monedas de 2 y mezclar hasta que se cae de cabeza. Yo, a continuación, repita el procedimiento hasta que me han dejado de $n$ veces.

$X_n$ es la variable aleatoria que cuenta el número de cabezas en el proceso. Mi objetivo es demostrar que con una probabilidad de $1-e^{-\Omega(n)}$ $X_n$ será en el intervalo de $[(1-\varepsilon)\mathbb{E}[X_n], (1+\varepsilon)\mathbb{E}[X_n]]$ fijos $\varepsilon>0$.

He observado que si $p_1<p_2$ sé que $np_1\leq\mathbb{E}[X_n]\leq np_2$ así que si de alguna manera se puede utilizar Chernoff o Azuma la desigualdad no necesito calcular la expectativa de $\mathbb{E}[X_n]$. He intentado buscar en este problema con las cadenas de Markov, pero no he tenido éxito allí. También he observado que para cada una de las $n$ I puede definir nuevas variables aleatorias $Y_{k,n}$ donde voy a tirar monedas de 1 $k$ los tiempos de la moneda y el 2 $n-k$ los tiempos y dejar de $Y_{k,n}$ denotar el número de cabezas que tengo que hacer. Entonces yo sé que para cada uno de los $n$ existe un único $k$ tal que $\mathbb{E}[Y_{k,n}]\leq \mathbb{E}[X_n] < \mathbb{E}[Y_{k+1,n}]$. Yo no puedo tomar ese enfoque, porque aunque no puedo encontrar lo adecuado de los límites de la variación de $X_n$

No le estoy pidiendo que estropear el problema para mí. Estoy preguntar simplemente si alguien podría empujar a mí en la dirección correcta.

Answer 1

Nos vamos a ir por las sugerencias a continuación. Una herramienta fundamental es $Y_n$ el número de lanzamientos entre el $(n-1)$th la cabeza y el $n$th la cabeza de la moneda de $2$. A continuación, $(Y_n)_{n\geqslant1}$ es un yo.yo.d. secuencia y uno puede fácilmente determinar su distribución. Para cada positivos $n$, vamos a $S_n=\sum\limits_{k=1}^nY_k$.

Ahora, $[X_n\geqslant2k]=[S_k\leqslant n]$ por lo tanto, para evaluar $\mathrm P(X_n\geqslant(1+\varepsilon)\mathrm E(X_n))$, se puede elegir algunos de los $k$ dependiendo $n$ tal que $2k\leqslant (1+\varepsilon)\mathrm E(X_n)$ y utilice el límite superior $$ \mathrm P(X_n\geqslant(1+\varepsilon)\mathrm E(X_n))\leqslant\mathrm P(S_k\leqslant n). $$ Del mismo modo, para evaluar $\mathrm P(X_n\leqslant(1-\varepsilon)\mathrm E(X_n))$, se puede elegir algunos de los $\ell$ dependiendo $n$ tal que $2\ell\geqslant (1-\varepsilon)\mathrm E(X_n)$ y utilice el límite superior $$ \mathrm P(X_n\leqslant(1-\varepsilon)\mathrm E(X_n))\leqslant\mathrm P(S_\ell\geqslant n). $$ Por lo que uno debe estimar la probabilidad de estos $S_k$ $S_\ell$ eventos. Este es el reino de las grandes desviaciones de la teoría , pero en una versión simple será suficiente para nosotros. Por ejemplo supongamos que uno quiere obligado $$ A=\mathrm P(S_k\leqslant n). $$ Tenga en cuenta que para todos no negativos $t$, $[S_k\leqslant n]=[\mathrm e^{-tS_k}\geqslant\mathrm e^{-tn}]$. Esta observación está en la base de los llamados Chernoff límites, en nuestro caso, $$ A=\mathrm P(\mathrm e^{-tS_k}\geqslant\mathrm e^{tn})\leqslant\mathrm e^{tn}\mathrm E(\mathrm e^{-tS_k})=\mathrm e^{tn}\mathrm E(\mathrm e^{-tY_1})^k. $$ Supongamos por un momento que $k=\alpha n+o(n)$ al$n\to\infty$, $A\leqslant\mathrm e^{-\Omega(n)}$ tan pronto como existe una no negativo $t$ tal que $$ \mathrm e^{t}\,\mathrm E(\mathrm e^{-tY_1})^\alpha \lt1. $$ Al $t\to0$, el lado izquierdo de esta desigualdad es $1+t-\alpha t\mathrm E(Y_1)+o(t)$ por tanto, un parámetro de $t$ existe tan pronto como $1-\alpha \mathrm E(Y_1)\lt0$. Usted sabe que el valor de $\mathrm E(Y_1)$ y la única condición en $\alpha $ es $$ 2\alpha n+o(n)\leqslant (1+\varepsilon)\mathrm E(X_n), $$ de ahí la prueba de que $A\leqslant\mathrm e^{-\Omega(n)}$ es completo si $$ (1+\varepsilon)\cdot\mathrm E(Y_1)\cdot\xi\gt2\quad \mbox{con}\quad \xi=\lim\limits_{n\to\infty}\frac{\mathrm E(X_n)}{n}. $$ Como usted probablemente ya habrá adivinado, sucede que $$ \mathrm E(Y_1)\cdot\xi=2, $$ por lo tanto, esta estrategia tiene éxito para cada positivos $\varepsilon$. De la misma manera por $B=\mathrm P(S_\ell\geqslant n)$.

La relación $\mathrm E(Y_1)\cdot\xi=2$ es el estándar de renovación de la teoría, pero permítanme terminar explicando la razón por la que lo lleva. En el largo plazo, por la mayoría de la clásica versión de la ley de los grandes números, se tarda alrededor de $n=\mathrm E(Y_1)\cdot N$ lanzamientos para $X$ a un aumento de $2N$ unidades, es decir, $X_n\approx 2N\approx 2n/\mathrm E(Y_1)$. Desde $X_n\approx\mathrm E(X_n)$, los rendimientos de $\xi=2/\mathrm E(Y_1)$.