1
$\begingroup$

I have a series of N Bernoulli tests (p, 1-p).

I need to calculate a probability of passing more than N/2 tests, depending on N and p.

The obvious solution is Chernoff bound: $\varepsilon \leq 2^{-N(p-\frac{1}{2})^2}$, but this is not sufficient for me. I actually need some stronger dependency on p. Is there any available?

I tried fitting Hoeffding, Azuma and Bernstein's inequalities, but it looks like all of these also do not give any sufficient dependency on p.

Is there any convenient estimation?

What I need is something like: $\varepsilon \leq 2^{-N*p}$

  • 0
    Are you looking for a better expansion in $p$ for $p$ close to $1/2$ or for $p$ close to $0$?2012-10-17
  • 0
    p closer to 0. Like, passing a test is highly improbable.2012-10-17

2 Answers 2