¿Cotación inferior para la suma de coeficientes binomiales?

Question

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.

Answer 1

En primer lugar, lo que da el límite de Stirling o el resultado de Stanica es ya una $(1+O(n^{-1}))$ aproximación de $\binom nk$ Por lo tanto, el único problema puede estar en la suma. No sé cómo hacerlo con tanta precisión, pero es fácil calcularlo hasta un factor constante aproximando con una serie geométrica:

$$\sum_{i\le k}\binom ni=\begin{cases}\Theta(2^n)&k\ge n/2-\sqrt n,\\\\\Theta\left(\left(1-\frac{2k}n\right)^{-1}\binom nk\right)&k\le n/2-\sqrt n.\end{cases}$$

De manera más general,

$$\sum_{i\le k}\binom ni(1-\epsilon)^{n-i}\epsilon^i=\begin{cases}\Theta(1)&k\ge\epsilon n-s,\\\\\Theta\left(\frac{\epsilon(n-k)}{\epsilon n-k}\binom nk(1-\epsilon)^{n-k}\epsilon^k\right)&k\le\epsilon n-s,\end{cases}$$

donde $s=\sqrt{n\epsilon(1-\epsilon)}$ . Véase el apéndice de mi documento http://math.cas.cz/~jerabek/papers/wphp.pdf .

Answer 2

En mi artículo "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copia en http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf Encuentro límites exactos agudos en esta suma. Tomando $p=1/2$ en el Teorema 2 da:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

donde:

• $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
• $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
• $Y(x) = Q(x)/\phi(x)$ , donde:
  • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
  • $Q(x) := \int_{x}^\infty \phi(u) du $
• $E(k; n,1/2)$ es el término de error, que se encuentra entre 0 y $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$ .
• $\sigma = \sqrt{n}/2$ .

El error relativo es como máximo $O(n^{-1/2})$ para todos $k$ mejor si $k$ no está cerca de $n/2$ .

Lo anterior requiere $\frac n2\le k\le n$ . Para $0\le k\lt \frac n2$ Utilizar $B(k;n,p) = 1 − B(n-k+1; n, 1-p)$ .

En algún lugar del arXiv hay un artículo que hace comparaciones numéricas de muchas de estas aproximaciones. No puedo encontrarlo ahora, tal vez alguien más pueda hacerlo.

Answer 3

¿Sabes lo bien que lo necesitas? Proporcionado $k < n/3$ digamos, un límite razonable (correcto dentro de un factor multiplicativo de 2) se obtiene tomando el último término $\binom {n}{k}$ (se ve esto porque se puede calcular el cociente de cada término con el término anterior y acotarlo arriba por 1/2. Ahora puedes estimar la suma como una serie geométrica).

Para $\sum_{j < k} \binom{n}{j}a^j(1-a)^{n-j}$ , delimitando por el último término también funciona bastante bien siempre que $k$ es un poco más pequeño que $an$ .

Answer 4

Aquí hay un documento relevante:

T. Worsch. "Límites inferiores y superiores para (sumas de) coeficientes binomiales". http://digbib.ubka.uni-karlsruhe.de/volltexte/181894

Answer 5

Suma de coeficientes binomiales $\sum_{i=0}^k\binom{n}{i}$ puede verse como la pregunta "¿cuántas cadenas binarias se acercan a la longitud- $n$ una cadena de ceros, que difiere como máximo en $k$ lugares". Se puede generalizar esto a alfabetos más grandes, y esto casi capta su pregunta sobre $\sum_{i=0}^k\binom{n}{i} (1-a)^{n-k}a^k$ . Así que, ¿quizás la comunidad de la teoría de la codificación tenga algo más que decir sobre esta cuestión?

Un lugar para empezar es este conjunto de notas de clase de Venkat Guruswami:

http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes2.pdf

(ver página 3).