## What is a Tail Bound?

The tails of a random variable X are those parts of the probability mass function far from the mean [1].

Sometimes we want to create **tail bounds** (or *tail inequalities*) on the PMF, or bound the probability that the random variable deviates a long way from the mean. For example, if the PMF represents a budget, we might not want to go over that budget by a factor of 3. Or, if I expect 10,000 people with student loans are in default, I might want to know the probability a million borrowers will default.

## Types of Tail Bound

Various formulas exist for tail bounds. One way to place a tail bound is by controlling the moments of the random variable X.

**Markovâ€™s inequality **is the simplest tail bound, only requiring the existence of the first moment. It states that, for a nonnegative random variable X with mean Î¼ = Îµ*X* [2],

**Pr(X â‰¥ k) â‰¤ Î¼/k. **

Although simple, the bounds that Markov’s inequality implies are usually not useful because they are too weak.

The** Chebyshev bound** is slightly stronger than Markov’s inequality. It is defined for a random variable X with mean Î¼ = ÎµX with standard deviation Ïƒ = âˆš(Îµ((X – Î¼)^{2})) for any Î´ â‰¥ 1:

**Pr(|X – Î¼ â‰¥ Î´Ïƒ) â‰¤ Î´ ^{-2}.**

## Gaussian Tail Bound via Chernoff

One of the more complex tail bounds is the **Chernoff bound**, which requires that the moment generating function exists. For many random variables, this requirement is usually not a problem because the MGF will exist in a neighborhood around 0 [3]. The Chernoff bound can be used to find a Gaussian tail bound and has several equivalent forms. One form is for Poisson trials X_{i} with sum X = Î£_{i}X_{i} and mean Î¼ = ÎµX, for any Î´ > 0:

## References

PMF Image: Qwfp, <https://creativecommons.org/licenses/by-sa/3.0>CC BY-SA 3.0 , via Wikimedia Commons

[1] Tail bounds. Retrieved November 28, 2021 from: https://courses.cs.washington.edu/courses/cse312/11au/slides/09tails.pdf

[2] Supplementary Lecture I: Tail Bounds. Retrieved November 28, 2021 from: http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/tailBounds.pdf

[3] Intermediate Statistics Fall 2019. Retrieved march 9, 2023 from http://www.stat.cmu.edu/~siva/705/lec2.pdf