Suma de variables aleatorias, al menos, $\log n$

Question

Deje $X_1,\dots,X_n$ ser independiente de las variables aleatorias en $\{0,1\}$, e $X=X_1+\dots+X_n$. Supongamos que $\mathbb{E}[X]=1$. ¿Cuál es la mejor cota superior de a $\text{Pr}(X>\log n)$?

El uso de la multiplicativo forma de Chernoff del obligado, tenemos que $\text{Pr}(X>1+\delta)<\dfrac{e^\delta}{(1+\delta)^{1+\delta}}$ cualquier $\delta>0$. Al$\delta$$\log n-1$, entonces esto se convierte en $\dfrac{e^{\log n-1}}{\log n^{\log n}}$. Esto es aproximadamente el $n^{1-\log\log n}$. Hay ejemplos de variables aleatorias $X_1,\dots,X_n$ que muestra que esta obligado resultante de Chernoff es (aproximadamente) de fuerte?

Answer 1

Este no es para todos los $n$, pero asintóticamente puedo conseguir una mejor, a continuación,$n^{1-\log\log n}$, aunque no es tan buena como la de Chernoff. Deje $X_i=1$ con una probabilidad de $\frac{1}{n}$. A continuación,$X=\text{Bin}(n,\frac{1}{n})$, que es aproximadamente el $\text{Poisson}(1)$ grandes $n$. Por lo tanto,$\mathbb{P}[X>\log n]\approx\sum_{i=\log n}^{\infty}\frac{e^{-1}}{i!}\approx \int_{\log n}^{\infty}\frac{e^{-1}}{\Gamma(x)}dx$. Vemos que, por la Regla de L'Hospital $\lim_{n\rightarrow\infty}\frac{\int_{\log n}^{\infty}\frac{e^{-1}}{\Gamma(x)}dx}{n^{1-\log log n}}=\frac{\frac{1}{n}\frac{1}{\Gamma(\log n)}}{e(\log\log n)n^{-\log log n}}\sim \frac{n^{log log n}}{en\log log n\sqrt{2\pi(\log n-1)}\left(\frac{\log (n-1)}{e}\right)^{\log (n-1)}}\sim\frac{n-1}{n\log\log n\sqrt{2\pi(\log n-1)}}\rightarrow 0$$n\rightarrow\infty$, $\sim$ me refiero a que me quitó un término cuyo límite era igual a 1 $n\rightarrow\infty$.