Hola, soy nuevo aquí. Sería genial si alguien sabe una buena respuesta.
¿Existe un buen límite inferior para la cola de las sumas de coeficientes binomiales? Estoy particularmente interesado en el caso más simple $\sum_{i=0}^k {n \choose i}$ . Sería muy bueno que el límite fuera lo suficientemente general como para aplicarlo a $\sum_{i=0}^k {n \choose i}(1-\epsilon)^{n-i}\epsilon^i$ .
Para el límite superior más comúnmente utilizado, se utilizan variantes de Chernoff, Hoeffding o las desigualdades más generales de Bernstein. Pero para el límite inferior, ¿qué podemos hacer?
Se podría utilizar Stirling para calcular $n!$ y luego ${n \choose k}$ y luego tomar la suma:
${n \choose k} = \frac{n!}{k!}{(n-k)!}$ y la fórmula de Stirling (una versión debida a Robbins) da $$n! = \sqrt{2\pi}n^{-1/2}e^{n-r(n)}$$ con el resto $r(n)$ Satisfaciendo a $\frac{1}{12n} \leq r(n) \leq \frac{1}{12n+1}$ .
Para el siguiente paso, es fácil aplicar Stirling tres veces. Pero, aún mejor, me he dado cuenta de que Stanica 2001 tiene una ligera mejora del límite inferior que también es más sencilla de enunciar (pero más difícil de demostrar):
$${n \choose k} \geq \frac{1}{\sqrt{2\pi}}2^{nH(k/n)}n^{1/2}k^{-1/2}(n-k)^{-1/2}e^{-\frac{1}{8n}}$$
para $H(\delta) = -\delta \log \delta -(1-\delta)\log(1-\delta)$ siendo la entropía de una moneda de probabilidad $\delta$ .
Ahora el paso 3. Si $k$ es pequeño, es razonable aproximar la suma por su mayor término, que debería ser el ${n \choose k}$ plazo a menos que $\epsilon$ es incluso menor que $k/n$ . Así que es genial, ¡hemos terminado!
Pero espera. Este límite está desviado por un factor de como máximo $\sqrt{n}$ . Sería mejor estar fuera de lugar por un máximo de $1 + O(n^{-1})$ como podríamos conseguir si tuviéramos la serie Taylor adecuada. ¿Existe una forma agradable de hacer la suma? ¿Debo calcular $\int_{0}^{k/n} 2^{nH(x)}\frac{1}{\sqrt{2\pi}}x^{-1/2}(1-x)^{-1/2}n^{1/2}e^{-1/8n} dx$ y compararlo con la suma discreta, e intentar acotar la diferencia? (Esta técnica ha funcionado para los límites de tipo Stirling.) (Los términos que no dependen de $k$ o $x$ se puede mover fuera de la integral).
Otro enfoque sería partir de Chernoff en lugar de Stirling (es decir, "¿Cómo se garantiza la estanqueidad de Chernoff, en función de n y k/n?")
¿Alguna idea o referencia? Gracias.
