aka concentration bound

Inequalities that tell you that most probability mass in some event space is concentrated in some region, so that something in that region occurs w.h.p.

• Markov's inequality – you know the mean, for a nonnegative r.v
• Chebyshev's inequality – you know the Standard deviation (which intuitively gives a notion of being close to the mean)
• Inequalities for sum of r.v.s
  • Hoeffding's inequality, Chernoff bound – for a sum of independent things (and having some sort of control over their variance/range!). As we use Exponential moments, the distribution of the individual r.v.s should have at least exponential tails. For heavier tails, we need other methods, like that using normal moments described below.
    • See extensions in Martingales (Azuma-Hoeffding inequality), where you have a sequence (stochastic process) where things can depend on past things (so non-independent r.v.s!), but the expecation of the future is always the same as the present, and other conditions.
  • For r.v.s with heavier tails (although it also works in general) [video], we can use the method of bounding moments moments rather than exponential moments, as is done for deriving Hoeffding-Chernoff bounds. So if we can bound the moments of the individual r.v.s (they don't vary too much!) in the sum, we can then bound the corresponding moments of the sum. It also gives a concentration bound that decays quadratic-exponentially (like for Hoeffding-Chernoff bounds), but not for too large deviations! (there is a version that works for larger deviations),. Under the assumptions of the theorem, the moments of the sum are sub-Gaussian. See notes here
    • for sum of independent exponential or power law distributed r.v.
• Bernstein inequalities
• Poincare inequalities Gives bound on variance (measure of how concentrated around mean r.v. is) (of the general form $variance(f) \lesssim \mathbf{E}[||gradient(f)||^2]$, see here). Useful when you can calculate the expected value of the gradient squared. From the variance, we can then use Chebysev's inequality to obtain probabilities.
  • Bounded differences inequality
  • Tensorization of variance

See here for description of the general phenomenon of concentration