2
$\begingroup$

I have $X_1,...$ Bernoulli variables with probability $p$ of success.

I want to get an $n$ such that with probability $\delta$

$P(\sum_{i=1}^n X_i \ge k) \ge \delta$

This $n$ would of course depend on $k$, $p$ and $\delta$. Can I get an upper bound for that $n(k,\delta,p)$? (meaning, I want some $n(k,\delta,p)$ for which the above holds, the smaller $n$ is, the better.)

Thanks.

$\endgroup$

2 Answers 2

3
$\begingroup$

Consult a discussion of Chernoff bounds like http://en.wikipedia.org/wiki/Chernoff_bound

$\endgroup$
1
$\begingroup$

The following observation, which is straightforward to derive, may be very useful here (also with regard to Naga's answer): $$ {\rm P}\bigg(\sum\limits_{i = 1}^n {(1 - X_i ) \ge n - k} \bigg) \le 1 - \delta $$ implies $$ {\rm P}\bigg(\sum\limits_{i = 1}^n {X_i \ge k} \bigg) \ge \delta. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .