Chernoff bound

Starts with Markov Inequalities and other tail inequalities and explains Chernoff Bounds in detail.

1. Chernoff Bound

2. Why? Markov Inequality Chernoff Bound Chernoff Bound : Proof Chernoff Bound : Applications References

3. Why?

4. What if you don’t know the pdf ? Limited information about the event is available and you want to bound the probability of that particular event We do not know the pdf or pmf of the random variable and we need to make some prediction Markov Inequality: how likely or unlikely actual value might deviate from the expected value.

5. Markov Inequality Definition Let X be an Independent Random Variable. E(x) : Expected Value of X a > 0 Pr(X ≥ a) ≤ E(x) /a (Most Generalised form ) If a = k E(x) , then Pr (X ≥ k E(x)) ≤ 1/k

6. Simple Proof

7. Chebyshev’s Inequality

8. Chernoff Bound statement

9. Proof

10. A small result

11. Also,

12. Minimize the upper bound

13. Proving the Chernoff bound

14. Other used forms

15. Example A biased coin flipped 200 times consecutively and comes up heads with probability 1/10 each time flipped find the upper bound probability that heads come more than120 times. Give the upper bound of the event using Markov inequality and Chernoff bound.

16. E(X) = np = 20 Markov bound => Pr (X ≥ 120) ≤ 1/6 Chernoff bound: Pr (X ≥ (1+5) E(x)) ≤ e ^-(25*20/7) ≤ e ^(-71.4) The Chernoff bound is a better upper bound than Markov inequality.

17. Applications Probabilistic method for proving randomised rounding algorithms like Approximate algorithm for Minimum congestion problem Approximate Algorithm for Vertex cover problem

18. Pr[ Xe > kC ∗ ] < 1 /n^3 Choose k in such manner that it satisfies the above condition.(We get a k approximation)

19. Rounding using Chernoff bound

20. References http://cseweb.ucsd.edu/~klevchen/techniques/chernoff.pdf http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf https://www.youtube.com/watch?v=sp9RF0zH-SU http://www.stat.cmu.edu/~larry/=stat705/Lecture2.pdf http://www.inf.ed.ac.uk/teaching/courses/dmmr/slides/13-14/chebi-Ch7.pdf http://www.faculty.jacobs-university.de/poswald/teaching/ESM2B/handouts/ProbabilityRandomProcessesBook.pdf

21. Thank you