Starfisher
New member
- Joined
- Oct 12, 2020
- Messages
- 1
Hi all,
Suppose [MATH]X_1 \dots X_n \sim \mathrm{Bernoulli}(p)[/MATH] are independent, for some [MATH]0 \le p < 1/2[/MATH]. Let [MATH]X[/MATH] denote their sum. I need an upper bound on [MATH]\Pr(X \ge n/4)[/MATH] that decays exponentially in [MATH]n[/MATH].
A simplified version of Chernoff's bound states that [MATH]\Pr(X \ge (1 + \delta)np) \le \exp \left ( - \frac{\delta ^ 2}{2 + \delta} np \right )[/MATH] for all [MATH]\delta \ge 0[/MATH]. (And this bound does decay exponentially in [MATH]n[/MATH] as I require.) Setting [MATH]\delta = \frac{1-4p}{4p}[/MATH] we find that [MATH]\Pr(X \ge (1+\delta)np) = \Pr(X \ge n/4)[/MATH], however I can't apply Chernoff's because this [MATH]\delta[/MATH] is negative for [MATH]1/4 < p < 1/2[/MATH].
How do I get around this problem?
Suppose [MATH]X_1 \dots X_n \sim \mathrm{Bernoulli}(p)[/MATH] are independent, for some [MATH]0 \le p < 1/2[/MATH]. Let [MATH]X[/MATH] denote their sum. I need an upper bound on [MATH]\Pr(X \ge n/4)[/MATH] that decays exponentially in [MATH]n[/MATH].
A simplified version of Chernoff's bound states that [MATH]\Pr(X \ge (1 + \delta)np) \le \exp \left ( - \frac{\delta ^ 2}{2 + \delta} np \right )[/MATH] for all [MATH]\delta \ge 0[/MATH]. (And this bound does decay exponentially in [MATH]n[/MATH] as I require.) Setting [MATH]\delta = \frac{1-4p}{4p}[/MATH] we find that [MATH]\Pr(X \ge (1+\delta)np) = \Pr(X \ge n/4)[/MATH], however I can't apply Chernoff's because this [MATH]\delta[/MATH] is negative for [MATH]1/4 < p < 1/2[/MATH].
How do I get around this problem?