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

Improve this question
$\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$
    – Brendan McKay
    Commented 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$
    – Emil Jeřábek
    Commented 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$
    – Navin Goyal
    Commented 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$
    – Navin Goyal
    Commented 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$
    – Navin Goyal
    Commented Aug 23, 2012 at 9:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .