I have a hw problem where it is asked to show theta(n) using chernoff bounds. I am able to prove for O(n) but not in the reverse way.Is it possible to prove both bounds using chernoff?
can chernoff bounds be used for proving upper bounds as well as lower bounds
0
$\begingroup$
probability-theory
probability-distributions
-
0What is the context? For eg, what is the hw problem? – 2012-03-12
1 Answers
1
It looks like it works in both directions. I never used it in the case of lower bound, but here Chernoff bound you can find example of usage as lower bound.
Let $X_{1}, ..., X_{n}$ be independent Bernoulli random variables, each having probability $p > 1/2$. Then the probability of simultaneous occurrence of more than $n/2$ of the events has an exact value $P$.
The Chernoff bound shows that P has the following lower bound.
$P \geq 1 - e ^{-2n(p-\frac{1}{2})^2}$