I'd like to compute $\sum_{i=0}^k {{N}\choose{i}}$. Is there a computable approximation for that?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ At first change your sigma to a definite integral by method of this post and after that use some approximation method about the definite integral. $\endgroup$– Amin235Commented Feb 5, 2017 at 12:31
-
7$\begingroup$ Possible duplicate of Sum of 'the first k' binomial coefficients for fixed n $\endgroup$– DirkCommented Feb 5, 2017 at 15:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
One of the more convenient and popular approximations of the sum is
$$\frac{2^{nH(\frac{k}{n})}}{\sqrt{8k(1-\frac{k}{n})}} \leq \sum_{i=0}^k\binom{n}{i} \leq 2^{nH(\frac{k}{n})}$$
for $0< k < \frac{n}{2}$, where $H$ is the binary entropy function. (The upper bound is exactly what Aryeh Kontorovich mentions.) You can find its proof in many textbooks, but probably I first learned it from Chapter 10 of The Theory of Error-Correcting Codes by MacWilliams and Sloane.
Also, this post on MO asks a similar question and is a good resource for the sum in my opinion. You can find several other useful bounds there.
answered Feb 5, 2017 at 15:26
-
$\begingroup$ Nice, I didn't know about the upper bound. That's probably as well as you can do, with such simple estimates. $\endgroup$ Commented Feb 5, 2017 at 15:41
-
$\begingroup$
$\endgroup$
1
A well-known upper bound, for $k\le N/2$, is $$ \sum_{i=0}^k {N\choose i} \le 2^{N H(k/N)},$$ where $H$ is the binary entropy function $$ H(x) = -x\log_2(x)-(1-x)\log_2(1-x).$$ This bound was sharpened in Lemma 5 of https://www.sciencedirect.com/science/article/pii/S0012365X12000544 ( Gottlieb, Lee-Ad; Kontorovich, Aryeh; Mossel, Elchanan, VC bounds on the cardinality of nearly orthogonal function classes, Discrete Math. 312, No. 10, 1766-1775 (2012). ZBL1242.05050.)
answered Feb 5, 2017 at 12:39
-
$\begingroup$ The sharpening adds a prefactor of $0.98$; the authors comment that a smaller prefactor is possible with a more careful/detailed proof. The paper is also available, open access, on arXiv: arxiv.org/abs/1007.4915; there it is Lemma 7.1, in Section 7 $\endgroup$– Sam OTCommented Aug 6, 2019 at 9:59