Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lower Bound on Binomial Distribution

  1. Jul 16, 2015 #1
    Hello all,

    Is there any lower bound on the following Binomial distribution

    [tex]\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}[/tex]

    as N goes to infinity and where epsilon is less that or equal 10^-3?

    Thanks
     
  2. jcsd
  3. Jul 16, 2015 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    It looks like the expression -> 0, for [itex]\epsilon \lt \frac{1}{2}[/itex].
     
  4. Jul 16, 2015 #3
    What if N is finite?
     
  5. Jul 16, 2015 #4
    I believe your expression tends to 0 as ##n \rightarrow \infty##, but I may be mistaking:

    Since ##0<\epsilon \le 0.001##, you get that ##0 < \epsilon^k \le \epsilon^{floor(N/2)+1} \le \epsilon ^{N/2}## and ## 0 < (1-\epsilon)^{N-k} \le 1 ##

    So that ##0\le \sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k} \le (2\sqrt{\epsilon})^N \rightarrow 0 ##
     
  6. Jul 17, 2015 #5
    The upper bound expression you reached is similar to something I have read. It was exactly:

    [tex]\left[2\sqrt{\epsilon(1-\epsilon)}\,\right]^N\frac{1-\epsilon}{\epsilon}[/tex]

    However, the latter is not a tight upper bound. Would your upper bound be a tight upper bound? In my case, epsilon is a Gaussian Q function, so what I did is that I took only ##\epsilon^L## where ##L=floor(N/2)+1##, and then used the Chernoff bound of the Q function as ##Q(x)\le e^{-x^2/2}##. But as you can see, I used first lower bound but then upper bound, which isn't right. However, I have found that this upper bound is a better upper bound than the upper bound I provided earlier by simulations. I need to check if yours is yet better.

    I need a lower bound for the Gaussian Q function then, or a new lower bound for the binomial distribution. Is there a simple one to find L or N in closed form given the lower bound, such that if the lower bound is ##LP=f(x,L)## I can find ##L=f^{-1}(LP,x)##?

    Thanks
     
    Last edited: Jul 17, 2015
  7. Jul 17, 2015 #6
    I am not competent to answer you about Chernoff bound, I don't know much about probabilities.
    There is an easy lower bound that is ##\epsilon^N## since you are summing positive terms.
     
  8. Jul 17, 2015 #7
    I need a tight lower bound. ##\epsilon^L## is better than ##\epsilon^N## as a lower bound, since ##\epsilon## is small, and thus the terms with lower exponents dominate the result.
     
  9. Jul 17, 2015 #8

    mathman

    User Avatar
    Science Advisor
    Gold Member

    I am relying on the law of large numbers. If the mean < 1/2, then the probability of the average of N samples > 1/2 goes to 0, as N becomes infinite.
     
  10. Jul 17, 2015 #9
    I think, since ##\epsilon## is small, we can just take the first term ##{N\choose L}\epsilon^L(1-\epsilon)^{N-L}##, which is approximated as a Gaussian random variable with mean ##N\epsilon## and variance ##N\epsilon(1-\epsilon)## as ##N## goes to ##\infty##. But this approximation is not helpful for me to find ##N##.
     
  11. Jul 18, 2015 #10

    mathman

    User Avatar
    Science Advisor
    Gold Member

    What N are you looking for? The question is: what happens when as [itex] N\to \infty[/itex]?
     
  12. Jul 23, 2015 #11
    Why ##(2\sqrt{\epsilon})^N \rightarrow 0 ## as ##N\rightarrow \infty##?
     
  13. Jul 23, 2015 #12

    mathman

    User Avatar
    Science Advisor
    Gold Member

    [itex]2\sqrt{\epsilon}<1[/itex]
     
  14. Jul 23, 2015 #13
    You asked me why I need to find N. My actual problem is that I have a limit on ##\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}\leq \eta##. I have two variables here ##\epsilon\leq 0.5## and ##N##, and ##\epsilon## is a function of ##N##. In particular, ##\epsilon=Q\left[\sqrt{\frac{2\,x/N}{y/N+1}}\right]##, where ##x## and ##y## are given, and ##Q[.]## is the ##Q## Gaussian function. I need to find ##N## such that the inequality holds. I said that ##\epsilon\leq 10^{-3}##, but actually, I don't have control over ##\epsilon##. All I know is that ##\epsilon\leq 0.5##. I think in this case, the asymptote doesn't hold always, does it?
     
  15. Jul 24, 2015 #14

    mathman

    User Avatar
    Science Advisor
    Gold Member

    You need [itex]\epsilon \lt 0.5[/itex], if = 0.5, it is ambiguous, since the law of large numbers requires an open interval <0.5 around [itex]\epsilon[/itex].
     
  16. Jul 24, 2015 #15
    I think we can safely assume it is less than 0.5.
     
  17. Jul 25, 2015 #16

    mathman

    User Avatar
    Science Advisor
    Gold Member

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Lower Bound on Binomial Distribution
  1. Upper bound/Lower Bound (Replies: 10)

  2. Binomial Distribution (Replies: 1)

  3. Binomial distribution (Replies: 3)

  4. Binomial distribution (Replies: 1)

Loading...