Concentration inequalities quantify how a random variable XX concentrates, or equivalently deviates, around its mean μ\mu. These concentration inequalities usually take the form

Pr⁡[∣X−μ∣≥t]≤(a function decreasing in t).\Pr[\lvert X - \mu \rvert \geq t] \leq (\text{a function decreasing in } t).

The specific function on the right-hand side depends on the assumptions made about XX. For example:

  • Markov’s inequality makes minimal assumptions about XX (only that it is non-negative) and yields a bound that decays as O(1t)O\left(\frac{1}{t}\right).
  • Chebyshev’s inequality assumes XX has finite mean μ\mu and variance σ2\sigma^2, yielding a bound that decays as O(1t2)O\left(\frac{1}{t^2}\right).
  • Chernoff’s inequality further assumes that XX is the sum of independent random variables, and yields a very tight bound that decay exponentially with increasing tt.

Markov’s inequality

Let XX be a non-negative random variable. Then, for any t>0t > 0, we have

Pr⁡[X≥t]≤E[X]t.\begin{aligned} \Pr[X \geq t] & \leq \frac{\mathbb{E}[X]}{t}. \end{aligned}

Fix t>0t > 0. We can write any real number xx as

x=1x<tx+1x≥tx.x = \mathbf{1}_{x<t}x + \mathbf{1}_{x \geq t}x.

Now consider E[X]\mathbb{E}[X]:

E[X]=E[1X<tX+1X≥tX]=E[1X<tX]+E[1X≥tX]≥E[1X≥tX](since X non-negative)≥E[1X≥tt]=t⋅E[1X≥t]=t⋅Pr⁡[X≥t].\begin{aligned} \mathbb{E}[X] & = \mathbb{E}\left[\mathbf{1}_{X<t}X + \mathbf{1}_{X \geq t}X\right] \\ &= \mathbb{E}\left[\mathbf{1}_{X<t}X\right] + \mathbb{E}\left[\mathbf{1}_{X \geq t}X\right] \\ & \geq \mathbb{E}\left[\mathbf{1}_{X \geq t}X\right] \quad (\text{since } X \text{ non-negative}) \\ & \geq \mathbb{E}\left[\mathbf{1}_{X \geq t}t\right] \\ & = t \cdot \mathbb{E}[\mathbf{1}_{X \geq t}] \\ & = t \cdot \Pr[X \geq t]. \end{aligned}

Dividing both sides by tt gives the desired result.

Chebyshev’s inequality

Let XX be a random variable with mean μ\mu and variance σ2\sigma^2. Then, for any t>0t > 0, we have

Pr⁡[∣X−μ∣≥t]≤σ2t2.\Pr\left[\lvert X - \mu \rvert \geq t\right] \leq \frac{\sigma^2}{t^2}.
Pr⁡[∣X−μ∣≥t]=Pr⁡[(X−μ)2≥t2]≤E[(X−μ)2]t2(Markov’s inequality)=σ2t2.\begin{aligned} \Pr\left[\lvert X - \mu \rvert \geq t\right] & = \Pr\left[(X - \mu)^2 \geq t^2\right] \\ & \leq \frac{\mathbb{E}[(X - \mu)^2]}{t^2} \quad (\text{Markov's inequality}) \\ & = \frac{\sigma^2}{t^2}. \end{aligned}

Chernoff’s inequality

Let XiX_i be independent Bernoulli random variables with parameters pip_i. Consider their sum SN=∑i=1NXiS_N = \sum_{i=1}^N X_i, and denote its mean by μ=E[SN]\mu = \mathbb{E}[S_N]. Then, for any t>μt > \mu, we have

Pr⁡[SN≥t]≤e−μ(eμt)t.\Pr[S_N \geq t] \leq e^{-\mu}\left(\frac{e\mu}{t}\right)^t.

The proof follows what is known as the “MGF method”. This method generally begins by writing the original inequality, multiplying both sides by a parameter λ>0\lambda > 0, exponentiating both sides, and then applying Markov’s inequality:

Pr⁡[SN≥t]=Pr⁡[eλSN≥eλt]≤E[eλSN]eλt(Markov’s inequality)=e−λtE[eλ∑i=1nXi]=e−λtE[∏i=1neλXi]=e−λt∏i=1nE[eλXi](Xi are independent).\begin{aligned} \Pr[S_N \geq t] & = \Pr\left[e^{\lambda S_N} \geq e^{\lambda t}\right] \\ & \leq \frac{\mathbb{E}\left[e^{\lambda S_N}\right]}{e^{\lambda t}} \quad (\text{Markov's inequality}) \\ & = e^{-\lambda t} \mathbb{E}\left[e^{\lambda \sum_{i=1}^{n} X_i}\right] \\ & = e^{-\lambda t} \mathbb{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right] \\ & = e^{-\lambda t} \prod_{i=1}^n\mathbb{E}\left[e^{\lambda X_i}\right] \quad (X_i \text{ are independent}). \end{aligned}

Note that each term inside the product, E[eλXi]\mathbb{E}\left[e^{\lambda X_i}\right], is the moment generating function (MGF) of XiX_i. The problem now reduces to bounding these MGFs. Recall that XiX_i is a Bernoulli random variable with parameter pip_i. Thus, we can bound each MGF as follows:

E[eλXi]=p(Xi=1)⋅eλ(1)+p(Xi=0)⋅eλ(0)=pieλ+(1−pi)=1+(eλ−1)pi≤e(eλ−1)pi(1+x≤ex for all x∈R).\begin{aligned} \mathbb{E}\left[e^{\lambda X_i}\right] & = p(X_i=1) \cdot e^{\lambda (1)} + p(X_i=0) \cdot e^{\lambda (0)} \\ &= p_i e^{\lambda} + (1-p_i) \\ &= 1 + (e^{\lambda} - 1)p_i \\ &\leq e^{(e^{\lambda} - 1)p_i} \quad (1 + x \leq e^x \text{ for all } x \in \mathbb{R}). \end{aligned}

Substituting this back into our previous inequality, we get

Pr⁡[SN≥t]≤e−λt∏i=1nE[eλXi]≤e−λt∏i=1ne(eλ−1)pi=e−λte∑i=1n(eλ−1)pi=e−λte(eλ−1)∑i=1npi=e−λte(eλ−1)μ.\begin{aligned} \Pr[S_N \geq t] &\leq e^{-\lambda t} \prod_{i=1}^n\mathbb{E}\left[e^{\lambda X_i}\right] \\ &\leq e^{-\lambda t} \prod_{i=1}^n e^{(e^{\lambda} - 1)p_i} \\ &= e^{-\lambda t} e^{\sum_{i=1}^n (e^{\lambda} - 1) p_i} \\ &= e^{-\lambda t} e^{(e^{\lambda} - 1) \sum_{i=1}^n p_i} \\ &= e^{-\lambda t} e^{(e^{\lambda} - 1) \mu}. \end{aligned}

Recall that λ>0\lambda > 0 is an arbitrary parameter. We can find the optimal λ\lambda that minimizes the right-hand side by differentiating with respect to λ\lambda and setting the derivative to zero:

ddλ(e−λt+(eλ−1)μ)=0  ⟺  (e−λt+(eλ−1)μ)(−t+μeλ)=0  ⟺  −t+μeλ=0  ⟺  eλ=tμ  ⟺  λ=ln⁡(tμ).\begin{aligned} \frac{d}{d\lambda} \left( e^{-\lambda t + (e^{\lambda} - 1) \mu} \right) &= 0 \\ \iff \left( e^{-\lambda t + (e^{\lambda} - 1) \mu} \right) \left( - t + \mu e^\lambda \right) &= 0 \\ \iff - t + \mu e^\lambda &= 0 \\ \iff e^\lambda &= \frac{t}{\mu} \\ \iff \lambda &= \ln\left(\frac{t}{\mu}\right). \end{aligned}

Substituting this optimal λ\lambda back into our previous inequality, we get

Pr⁡[SN≥t]≤e−λte(eλ−1)μ=e−ln⁡(tμ)te(tμ−1)μ=(tμ)−tet−μ=(μt)tete−μ=(eμt)te−μ.\begin{aligned} \Pr[S_N \geq t] &\leq e^{-\lambda t} e^{(e^{\lambda} - 1) \mu} \\ & = e^{-\ln\left(\frac{t}{\mu}\right) t} e^{\left(\frac{t}{\mu} - 1\right) \mu} \\ & = \left(\frac{t}{\mu}\right)^{-t} e^{t -\mu}\\ & = \left(\frac{\mu}{t}\right)^{t} e^{t} e^{-\mu}\\ & = \left(\frac{e \mu}{t}\right)^{t} e^{- \mu}. \end{aligned}

Let XiX_i be independent Bernoulli random variables with parameters pip_i. Consider their sum SN=∑i=1NXiS_N = \sum_{i=1}^N X_i, and denote its mean by μ=E[SN]\mu = \mathbb{E}[S_N]. Then, for any δ>0\delta > 0, we have

Pr⁡[SN≥(1+δ)μ]≤exp⁡(−δ2μ2+δ).\Pr\left[ S_N \geq (1 + \delta) \mu \right] \leq \exp\left( - \frac{ \delta^2 \mu }{ 2 + \delta } \right).

Let t=(1+δ)μt = (1 + \delta) \mu. Plugging into Chernoff’s inequality, we get

Pr⁡[SN≥(1+δ)μ]≤e−μ(eμ(1+δ)μ)(1+δ)μ=e−μ(e1+δ)(1+δ)μ=e−μ+(1+δ)μln⁡(e1+δ)=exp⁡(−μ+(1+δ)μ(1−ln⁡(1+δ)))=exp⁡(−μ+(1+δ)μ−(1+δ)μln⁡(1+δ))=exp⁡(δμ−(1+δ)μln⁡(1+δ))=exp⁡(−μϕ(δ))(letting ϕ(δ):=(1+δ)ln⁡(1+δ)−δ)≤exp⁡(−δ2μ2+δ)(since ϕ(δ)≥δ22+δ).\begin{aligned} \Pr\left[ S_N \geq (1 + \delta) \mu \right] & \leq e^{-\mu} \left( \frac{e\mu}{(1 + \delta)\mu} \right)^{(1 + \delta)\mu} \\ & = e^{-\mu} \left( \frac{e}{1 + \delta} \right)^{(1 + \delta)\mu} \\ &= e^{ - \mu + (1 + \delta) \mu \ln\left( \dfrac{ e }{ 1 + \delta } \right) } \\ &= \exp\left( - \mu + (1 + \delta) \mu \left( 1 - \ln(1 + \delta) \right) \right) \\ &= \exp\left( - \mu + (1 + \delta) \mu - (1 + \delta) \mu \ln(1 + \delta) \right) \\ &= \exp\left( \delta \mu - (1 + \delta) \mu \ln(1 + \delta) \right) \\ &= \exp\left(- \mu \phi(\delta)\right) \quad (\text{letting } \phi(\delta) := (1 + \delta) \ln(1 + \delta) - \delta) \\ &\leq \exp\left( - \frac{ \delta^2 \mu }{ 2 + \delta } \right) \quad (\text{since } \phi(\delta) \geq \frac{ \delta^2 }{ 2 + \delta }). \end{aligned}

It remains to show that ϕ(δ)≥δ22+δ\phi(\delta) \geq \frac{ \delta^2 }{ 2 + \delta } for all δ>0\delta > 0.

Expand to see details.

Define f(δ):=ϕ(δ)−δ22+δ=(1+δ)ln⁡(1+δ)−δ−δ22+δf(\delta) := \phi(\delta) - \frac{ \delta^2 }{ 2 + \delta } = (1 + \delta) \ln(1 + \delta) - \delta - \frac{ \delta^2 }{ 2 + \delta }. It suffices to show that f(δ)≥0f(\delta) \geq 0 for all δ>0\delta > 0.

First, note that f(0)=(1+0)ln⁡(1+0)−0−022+0=0f(0) = (1 + 0) \ln(1 + 0) - 0 - \frac{0^2}{2 + 0} = 0.

Next, we compute the derivative f′(δ)f'(\delta):

f′(δ)=(1)ln⁡(1+δ)+(1+δ)11+δ−1−(2+δ)(2δ)−(δ2)(1)(2+δ)2=ln⁡(1+δ)−4δ+δ2(2+δ)2.\begin{aligned} f'(\delta) &= (1) \ln(1 + \delta) + (1+\delta)\frac{1}{1 + \delta} - 1 - \frac{ (2+ \delta) (2\delta) - (\delta^2)(1)}{ (2 + \delta)^2 } \\ & = \ln(1 + \delta) - \frac{ 4\delta + \delta^2 }{ (2 + \delta)^2 }. \end{aligned}

Next, we compute the second derivative f′′(δ)f''(\delta):

f′′(δ)=11+δ−(2+δ)2(4+2δ)−(4δ+δ2)(4+2δ)(2+δ)4=11+δ−2(2+δ)3−2(4δ+δ2)(2+δ)(2+δ)4=11+δ−2(2+δ)2−2(4δ+δ2)(2+δ)3=11+δ−8+8δ+2δ2−8δ−2δ2(2+δ)3=11+δ−8(2+δ)3.\begin{aligned} f''(\delta) &= \frac{1}{1 + \delta} - \frac{(2+\delta)^2(4 + 2\delta) - (4\delta + \delta^2)(4 + 2\delta)}{(2+\delta)^4} \\ &= \frac{1}{1 + \delta} - \frac{2(2+\delta)^3 - 2(4\delta + \delta^2)(2 + \delta)}{(2+\delta)^4} \\ &= \frac{1}{1 + \delta} - \frac{2(2+\delta)^2 - 2(4\delta + \delta^2)}{(2+\delta)^3} \\ &= \frac{1}{1 + \delta} - \frac{8 + 8\delta + 2\delta^2 - 8\delta - 2\delta^2}{(2+\delta)^3} \\ &= \frac{1}{1 + \delta} - \frac{8}{(2+\delta)^3}. \end{aligned}

We want to show that 11+δ−8(2+δ)3≥0\frac{1}{1 + \delta} - \frac{8}{(2+\delta)^3} \geq 0:

11+δ−8(2+δ)3≥0  ⟺  11+δ≥8(2+δ)3  ⟺  (2+δ)3≥8(1+δ)  ⟺  (8+12δ+6δ2+δ3)≥8+8δ  ⟺  (8+12δ+6δ2+δ3)−(8+8δ)≥0  ⟺  4δ+6δ2+δ3≥0.\begin{aligned} \frac{1}{1 + \delta} - \frac{8}{(2+\delta)^3} &\geq 0 \\ \iff \frac{1}{1 + \delta} &\geq \frac{8}{(2+\delta)^3} \\ \iff (2 + \delta)^3 &\geq 8(1+\delta) \\ \iff (8 + 12\delta + 6\delta^2 + \delta^3) &\geq 8 + 8\delta \\ \iff (8 + 12\delta + 6\delta^2 + \delta^3) - (8 + 8 \delta) &\geq 0\\ \iff 4\delta + 6\delta^2 + \delta^3 &\geq 0. \end{aligned}

The last inequality is clearly true for all δ>0\delta > 0. Thus, f′′(δ)≥0f''(\delta) \geq 0 for all δ>0\delta > 0.

From f(0)=0f(0) = 0, f′(0)=0f'(0) = 0, and f′′(δ)≥0f''(\delta) \geq 0, it follows that f(δ)≥0f(\delta) \geq 0 for all δ>0\delta > 0. Thus, ϕ(δ)≥δ22+δ\phi(\delta) \geq \frac{ \delta^2 }{ 2 + \delta } for all δ>0\delta > 0.

This concludes the proof.

References

References are listed in alphabetical order.

  1. High-dimensional probability: An introduction with applications in data science [link]
    Roman Vershynin. Cambridge University Press. 2026.