MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f^B_{j,a}(s)$ be the probability mass function of the binomial distribution, that is $f^B_{j,a}(s) = {j \choose s} a^s (1-a)^{j-s}$. And let $F^B_{j+1,b}(s)$ be the cdf of the binomial distribution, that is $F^B_{j+1,b}(s) = \sum_{i=0}^{s} f^B_{j+1,b}(i)$.

In my research, I need a quite precise upper bound on the sum

$$\sum_{s=0}^j \frac{f^B_{j,a}(s)}{F^B_{j+1,b}(s)}.$$

For $a>b$, a useful upper bound would be $1 + O(e^{-(a-b)^2j})$ for $j > 1/(a-b)$. That this bound could be true is supported by experiments (although not very extensive). We can prove the bound $1 + O(e^{-(a-b)^2j})$ on the part of the above sum from $s=\lceil bj \rceil$ to $j$. But for the remaining part of the sum we can only obtain a bound of $O(\frac{e^{-(a-b)^2j}}{a-b})$.

One difficulty in bounding the above sum is that we don't know good lower bounds for $F^B_{j+1,b}(s)$ for small $s$.

share|cite|improve this question
the summation in the definition of $F_{j+1,b}^B(s)$ is over $i$, but the summands do not depend on $i$. It looks like a misprint. – Fedor Petrov Aug 6 '12 at 11:53
You are right. It's corrected. – Navin Goyal Aug 7 '12 at 4:36
and should the definition of $f$ have $(1-a)^{j-s}$ rather than $(1-a)^s$? – Brendan McKay Aug 7 '12 at 6:39
For small $s$ (rather smaller than $jb$) a good lower bound on $F_{j+1,b}(s)$ is its largest term. – Brendan McKay Aug 7 '12 at 6:43
Hi Navin, welcome to MO! Lower bound on $F^B_{j+1,b}(s)$ tight up to a constant multiple is mentioned in, though it may not be enough for your purposes. – Emil Jeřábek Aug 7 '12 at 13:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.