Lanzando repetidamente un dado y las colas de la distribución multinomial.

Question

Para $1 \leq i \leq n$ deja $X_i$ sean variables aleatorias independientes, y que cada una $X_i$ ser la distribución uniforme en el set ${0,1,2, \dots ,m}$ para que $X_i$ es como un $m+1$ y la muerte de un lado. Deje que $$Y= \frac {1}{n} \sum_ {i=1}^n \frac {1}{m} X_i,$$ para que $ \mathbb {E}(Y)= \frac {1}{2}$ . Estoy interesado en las colas de esta distribución, que es el tamaño de $$ \Pr\left ( Y \geq k \right )$$ donde $ \frac {1}{2}< k \leq 1$ es una constante.

En el caso de que $m=1$ estamos viendo la distribución del binomio, y $$ \Pr\left ( Y \geq k \right )= \frac {1}{2^n} \sum_ {i=0}^{(1-k) n} \binom {n}{i}$$ y podemos atar esto por encima de $(1-k)n \binom {n}{(1-k)n}$ y abajo por $ \binom {n}{(1-k)n}$ que da lugar a $$ \Pr\left ( Y \geq k \right ) \approx \frac {1}{2^n} e^{n H(k)}$$ donde $H(x)=- \left (x \log x+(1-x) \log (1-x) \right )$ es la función de entropía. (Yo uso aprox. libremente)

¿Qué tipo de límites similares tenemos en las colas de esta distribución cuando $m \geq 2$ ? Busco usar las propiedades multinomiales explícitas para obtener algo más fuerte que lo que obtendrías usando Chernoff de Hoeffding.

Answer 1

La variación de $X_i$ es $ \frac {m(m+2)}{12}$ así que de $Y$ es $ \frac {m+2}{12mn}$ . El teorema del límite central lleva a una aproximación normal para los casos de moderados a altos $n$

$$ \Pr\left ( Y \geq k \right ) \approx 1 - \Phi\left ((2k-1){ \sqrt { \frac {3mn}{m+2}}} \right )$$

El método de Stein y otros métodos similares pueden ayudar a calcular las tasas de convergencia

Answer 2

Considere algunas variables aleatorias de i.i.d. $ \xi $ y $( \xi_n )_{n \geqslant1 }$ con la media $ \mathrm E( \xi )=0$ y el momento exponencial finito $ \mathrm E( \mathrm e^{t| \xi |})$ para cada $t$ . Entonces, por cada $x \gt0 $ existe $I(x) \gt0 $ de tal manera que, cuando $n \to\infty $ , $$ \mathrm P( \xi_1 + \cdots + \xi_n\geqslant nx)= \mathrm e^{-nI(x)+o(n)}. $$ Además, la optimización del límite superior del exponencial de Chernoff produce el valor exacto del exponente $I(x)$ . A saber, recuerde que, por cada no negativo $t$ , $$ \mathrm P( \xi_1 + \cdots + \xi_n\geqslant nx) \leqslant\left ( \mathrm e^{-tx} \mathrm E( \mathrm e^{t \xi }) \right )^n= \mathrm e^{-nI(t,x)}, $$ donde $$ I(t,x)=tx- \log\mathrm E( \mathrm e^{t \xi }), $$ y sucede que $$ I(x)= \sup\limits_ {t \geqslant0 }I(t,x). $$ Tengan en cuenta que $ \mathrm E( \xi )=0$ por lo tanto $ \mathrm E( \mathrm e^{t \xi })=1+o(t)$ cuando $t \to0 $ y $I(t,x)=tx+o(t)$ . En particular, $I(t,x) \gt0 $ para $t \gt0 $ lo suficientemente pequeño, por lo tanto $I(x) \gt0 $ y el límite superior de arriba no es trivial.

Como ya se ha dicho, este límite superior también proporciona el comportamiento exacto, en la escala exponencial, de la probabilidad de que la evento de grandes desviaciones considerado, es decir, $$ \lim\limits_ {n \to\infty } \frac1n\log\mathrm P( \xi_1 + \cdots + \xi_n\geqslant nx)=-I(x). $$ En su entorno, uno considera $ \xi = \frac1mX - \frac12 $ y $x=k- \frac12 $ por lo tanto $0 \lt x \lt\frac12 $ . Note finalmente que, en general, $I(x)=I(t_x,x)$ donde $t_x$ resuelve la ecuación $ \partial_tI (t,x)=0$ es decir.., $$ x \mathrm E( \mathrm e^{t \xi })= \mathrm E( \xi\mathrm e^{t \xi }). $$