2
$\begingroup$

What are the most elegant approximations by using Stirling's approximation for the sum of binomial terms as below?

$Sum(r) = \sum\limits_{k=r}^{n} \binom{n}{k} p^k (1-p)^{n-k}$

I tried to plug in the approximation of factorial $x!$ into the formula, but the result looks crazily clumsy. Is there any elegant way to do this?

Many thanks!

$\endgroup$
  • $\begingroup$ There are a lot of different approximations depending on the precise range you want. For your purposes how large is $r$? If $r$ is close to $n$ then this is easier to approximate. $\endgroup$ – JoshuaZ Sep 9 '18 at 21:15
  • $\begingroup$ Many thanks for your reply. $r$ would be half of $n$. A typical one would be $\frac {n+1}{2}$ when $n$ is odd. $\endgroup$ – H42 Sep 9 '18 at 21:41
2
$\begingroup$

From 'Decoding Generalized Hyperoctohedral Groups and Asymptotic Analysis of Correctible Error Patterns,' R. Bailey and T. Prellberg, Contribut. Discrete Math. vol. 7 # 1, p 1-14 (2012). The following asymptotic expression is derived:

Define $$ F_{m,r}(x)=\sum_{k=0}^r{\binom{m}{k}x^k} $$ $$ \beta=r/m \text{ with } 0<\beta<1$$ $$ \rho(\beta,x)=\sqrt{\log{(1+x)} - \beta \, \log{x} + \beta\log{\beta} + (1-\beta)\log{(1-\beta}) } $$ Then $$ F_{m,r}(x) \sim (1+x)^m \frac{1}{2} \text{erfc}\big( \sqrt{m}\, \rho(\beta, x) \big) $$ The paper gives the next term in the expansion as well. The sign associated with $\rho$ because of the square root is tricky. I did the math once and I believe it is equivalent to $\text{sign}(x-\beta/(1-\beta))$.

Your problem can be reduced to this one by using the full binomial theorem and subtracting the 'head' of the series. Of course, to use this formula $x=p/(1-p)$ and there will be an external factor of $(1-p)^n.$

Comment: 9/26/2018

When I wrote this I tested the approximation with $\beta$ > 0.6 and for several $0<x<1.$ In this region the formula appears to work well. For $\beta$ < 1/2 and $x$ in the upper range, this formula seems to be off by a factor that can get disturbingly high. For example, let m=400 and r=50. Then for x=1/10 $F_{400,50}(1/10)/'approx' = 1.0029$, acceptable to me for most situations. However for x=9/10 and the same m,n, $F_{400,50}(9/10)/'approx' = 2.685.$ I would not find this discrepancy satisfactory. There must be some implicit assumption in the paper's setup that precludes this formula from being universally applicable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.