Concentration bounds
The question of interest is the probability, or rather a bound on the probability that the random variable (either runtime or correctness) of a randomized algorithm will behave as expected. In this lecture we will talk about some inequalities that help us tighten this bound
Markov’s inequality
Chebyshev’s inequality
Higher moments
Mill’s inequality
Given the well known bounds on Gaussian distribution, we can see that Chebyshev’s inequality is not tight. So we devise another.