0
$\begingroup$

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?

  • 0
    What is the context? For eg, what is the hw problem?2012-03-12

1 Answers 1

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}$