3
$\begingroup$

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$.

$\endgroup$
5
  • 1
    $\begingroup$ For small $s$ (rather smaller than $jb$) a good lower bound on $F_{j+1,b}(s)$ is its largest term. $\endgroup$ Aug 7, 2012 at 6:43
  • 1
    $\begingroup$ Hi Navin, welcome to MO! Lower bound on $F^B_{j+1,b}(s)$ tight up to a constant multiple is mentioned in mathoverflow.net/questions/55617, though it may not be enough for your purposes. $\endgroup$ Aug 7, 2012 at 13:07
  • $\begingroup$ @Brendan McKay: Thanks for pointing out the error; I've corrected it. The lower bound you pointed out gives the weaker lower bound with a-b in the denominator (as mentioned in my question). $\endgroup$ Aug 8, 2012 at 8:15
  • $\begingroup$ @ Emil Jeřábek: Thanks Emil; unfortunately it does look like a constant factor is too weak for my purpose. $\endgroup$ Aug 8, 2012 at 8:17
  • $\begingroup$ @Emil: It seems that your bound in answer to another MO question that you linked to, can be useful. However, there seems to be some discrepancy between the bound you state in your answer and the bound in your paper. Bound in the paper (in the notation of your MO answer): $$\frac{(1-\epsilon)k}{\epsilon n -k} {n \choose k}\epsilon^k (1-\epsilon)^{n-k}.$$ And the bound in your answer: $$\frac{\epsilon (n-k)}{\epsilon n -k} {n \choose k}\epsilon^k (1-\epsilon)^{n-k}.$$ These two can differ by more than a constant factor. Am I missing something? $\endgroup$ Aug 23, 2012 at 9:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.