Límites para estar muy lejos de la media

Question

Si tiro $n$ monedas cada una con probabilidad $1/\sqrt{n}$ de conseguir una cabeza, me gustaría saber los límites de la probabilidad de conseguir $n/2$ o más cabezas. Es evidente que el número medio de cabezas es $\sqrt{n}$ . Parece que se puede utilizar el forma multiplicativa del límite de Chernoff ¿pero sigue siendo válida cuando se está tan lejos de la media? La definición de la wikipedia no lo aclara.

Answer 1

Esta es también una posible aplicación para La desigualdad de Hoeffding . Pero debo admitir que no conozco tan bien el límite de Chernoff, tal vez sea más nítido. (De hecho, lo busqué sólo después de escribir mi respuesta y parece una versión especializada de la desigualdad de Hoeffding y por lo tanto podría ser más agudo).

Dejemos que $X_1,\ldots,X_n$ denotan variables aleatorias independientes con a $\mathrm{Bi}(1,1/\sqrt{n})$ distribución. Cada $X_i$ está acotado entre cero y uno. Si dejamos que $S_n=X_1+\ldots+X_n$ entonces por la desigualdad de Hoeffding, $$P(S_n-ES_n\geq t) \leq \exp\{-2t^2/n\}\, \text{for all }t>0\,.$$ Ahora $ES_n=\sqrt{n}$ Así que $S_n\geq n/2$ equivale a $S_n-\sqrt{n}\geq n/2-\sqrt{n}$ . Así que queda por conectar $t=n/2-\sqrt{n}$ en la desigualdad de Hoeffding. Si no me equivoqué, terminamos con $$P(S_n\geq n/2)\leq \exp\{-n/2+2\sqrt{n}-2\}\, \text{for all } n>4\,, $$ la restricción de $n$ siendo debido a la positividad requerida de $t$ .

Para muestras pequeñas y no tan pequeñas (no sé si un resultado numérico también podría ser interesante para ti o si necesitas un resultado teórico), un cálculo exacto usando la distribución binomial no es en absoluto un problema. Añadiré los resultados numéricos como una edición.

Editar:

Podemos comparar los resultados exactos con la desigualdad de Hoeffding de la siguiente manera:

p.exact <- function(n) 1-pbinom(floor((n-1)/2),n,1/sqrt(n))
hoeffding <- function(n) exp(-n/2+2*sqrt(n)-2)
N <- 40
lst <- data.frame(cbind(n=1:N,exact=1:N,hoeffding=1:N))
for (i in 1:N) {
    lst[i,2] <- p.exact(i)
    lst[i,3] <- hoeffding(i)
}
lst

plot(exact~n,data=lst,type="l",ylab="probability")
lines(lst$n[5:N],lst$hoeffding[5:N],lty=3)
legend("topright",legend=c("Binomial","Hoeffding"),lty=c(1,3))

que da el siguiente gráfico:

Se puede ver que para tamaños de muestra pequeños, sería bueno realizar los cálculos exactos. Las diferencias para valores más grandes ya no son bien visibles, se podría por ejemplo graficar la relación de los dos valores si uno está interesado en estas cosas.