Concentration Inequalities

Markov’s inequality

For any non-negative random variable $X$ and $t>0$, we have

$$\mathbb{P}\{X\ge t\}\le \frac{\mathbb{E}X}{t}.$$

Proof

Fix any $t>0$. We can represent any real number as

$$x=x\cdot 1\{x\ge t\}+x\cdot 1\{x<t\}.$$

Then we have

$$\begin{array}{rl}\mathbb{E}X& =\mathbb{E}(X\cdot 1\{X\ge t\})+\mathbb{E}(X\cdot 1\{X<t\})\\ & \ge \mathbb{E}(t\cdot 1\{X\ge t\})\\ & =t\cdot \mathbb{E}1\{X\ge t\}=t\cdot \mathbb{P}\{X\ge t\}\square \end{array}$$

---

Chebyshev’s inequality

Let $X$ any random variable. Then, for every $t>0$ we have

$$\mathbb{P}\{|X-\mathbb{E}X|\ge t\}\le \frac{\text{Var}(X)}{t^2}.$$

Proof

By using Markov’s inequality on the non-negative random variable $(X-\mathbb{E}X{)}^2$ we have

$$\mathbb{P}\{|X-\mathbb{E}X|\ge t\}=\mathbb{P}\{(X-\mathbb{E}X{)}^2\ge t^2\}\le \frac{\mathbb{E}(X-\mathbb{E}X{)}^2}{t^2}=\frac{\text{Var}(X)}{t^2}\square$$

---

Chernoff’s inequality

Let $X_i$ be $N$ independent Bernoulli random variables with parameters $p_i$. Let $S_N=X_1+\cdots +X_N$, with mean $\mu =\mathbb{E}{S}_N$.

Then, for every value $t>\mu$, we have

$$\mathbb{P}\{S_N\ge t\}\le e^{-\mu }{\left(\frac{e\mu }{t}\right)}^t$$

Proof

We use the same approach as for the Chernoff’s inequality, passing through the Markov’s inequality.

$$\begin{array}{rl}\mathbb{P}\{S_N\ge t\}& =\mathbb{P}\left\{e^{\lambda S_N}\ge e^{\lambda t}\right\}\le e^{-\lambda t}\mathbb{E}{e}^{\lambda S_n}\\ & =e^{-\lambda t}\mathbb{E}\prod _{i=1}^N{e}^{\lambda X_i}=e^{-\lambda t}\prod _{i=1}^N\mathbb{E}{e}^{\lambda X_i}\\ & =e^{-\lambda t}\prod _{i=1}^N\left(e^{\lambda }{p}_i+(1-p_i)\right)\\ & =e^{-\lambda t}\prod _{i=1}^N\left(1+(e^{\lambda }-1)p_i\right)\\ & \le e^{-\lambda t}\prod _{i=1}^N\exp \left((e^{\lambda }-1)p_i\right)\end{array}$$

where last inequality holds since $1+x\le e^x$ for every $x\in \mathbb{R}$.

Therefore

$$\begin{array}{rl}\mathbb{P}\{S_N\ge t\}& \le e^{-\lambda t}\prod _{i=1}^N\exp \left((e^{\lambda }-1)p_i\right)\\ & =e^{-\lambda t}\exp \left(\sum _{i=1}^N(e^{\lambda }-1)p_i\right)\\ & =e^{-\lambda t}\exp \left((e^{\lambda }-1)\sum _{i=1}^N{p}_i\right)\\ & =e^{-\lambda t}\exp \left((e^{\lambda }-1)\mu \right)\\ & =\exp \left((e^{\lambda }-1)\mu -\lambda t\right)\end{array}$$

Since this function is convex, we can minimize the bound finding the value of $\lambda$ s.t. the first derivative becomes $0$. By monotonicity, it holds when the first derivative of the $(e^{\lambda }-1)\mu -\lambda t$ is $0$, i.e., when

$$e^{\lambda }\mu -t=0⟺\lambda =\ln \frac{t}{\mu }$$

Finally

$$\begin{array}{rl}\mathbb{P}\{S_N\ge t\}& \le \exp \left(\left(\frac{t}{\mu }-1\right)\mu -t\ln \frac{t}{\mu }\right)\\ & =\exp \left(t-\mu -t\ln \frac{t}{\mu }\right)\\ & =e^t{e}^{-\mu }{\left(\frac{t}{\mu }\right)}^t\\ & =e^{-\mu }{\left(\frac{et}{\mu }\right)}^t\end{array}$$

In a similar way, we can prove the lower tail bound:

$$\mathbb{P}\{S_N\le t\}\le e^{-\mu }{\left(\frac{e\mu }{t}\right)}^t$$

Chernoff’s inequality: small deviations

Let $X_i$ be $N$ independent Bernoulli random variables with parameters $p_i$. Let $S_N=X_1+\cdots +X_N$, with mean $\mu =\mathbb{E}{S}_N$.

Then, for every $\delta \in \left(0,1\right]$ we have

$$\mathbb{P}\{|S_N-\mu |\ge \delta \mu \}\le 2e^{-c\mu {\delta }^2}$$

where $c>0$ is an absolute constant.

Proof

We can re-write the probability

$$\begin{array}{rl}\mathbb{P}\{|S_N-\mu |\ge \delta \mu \}& =\mathbb{P}\{S_N-\mu \ge \delta \mu \}+\mathbb{P}\{S_N-\mu \le -\delta \mu \}\\ & =\mathbb{P}\{S_N\ge (1+\delta )\mu \}+\mathbb{P}\{S_N\le (1-\delta )\mu \}\\ & \\ & \le e^{-\mu }{\left(\frac{e\mu }{\mu (1+\delta )}\right)}^{\mu (1+\delta )}+e^{-\mu }{\left(\frac{e\mu }{\mu (1-\delta )}\right)}^{\mu (1-\delta )}\\ & =e^{-\mu }{\left[{\left(\frac{e}{1+\delta }\right)}^{1+\delta }\right]}^{\mu }+e^{-\mu }{\left[{\left(\frac{e}{1-\delta }\right)}^{1-\delta }\right]}^{\mu }\\ & ={\left[e^{-1}\cdot {\left(\frac{e}{1+\delta }\right)}^{1+\delta }\right]}^{\mu }+{\left[e^{-1}\cdot {\left(\frac{e}{1-\delta }\right)}^{1-\delta }\right]}^{\mu }\\ & ={\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }+{\left(\frac{e^{-\delta }}{(1-\delta {)}^{1-\delta }}\right)}^{\mu }\\ & =p_1+p_2\end{array}$$

We want now to maximize $p_1$ and $p_2$, and this is equivalent to maximize $\log p_1=\mu (\delta -(1+\delta )\log (1+\delta ))$ and $\log p_2=\mu (-\delta -(1-\delta )\log (1-\delta ))$.

here.

$$\frac{x}{1+\frac{x}{2}}\le \log (1+x)\le \frac{x+\frac{x^2}{2}}{1+x}$$

And

$$\log (1-x)\ge \frac{\frac{x^2}{2}-x}{1-x}$$

Since $\log (1+x)\ge \frac{x}{1+x/2}$, then

$$\begin{array}{rl}\log p_1& \le \mu \left(\delta -\frac{(1+\delta )\cdot \delta }{1+\delta /2}\right)\\ & =\delta \mu \left(1-\frac{(1+\delta )}{1+\delta /2}\right)\\ & =\delta \mu \left(-\frac{\delta /2}{1+\delta /2}\right)\\ (\delta \le 1)& \le \delta \mu \left(-\frac{\delta /2}{3/2}\right)\\ & =-\frac{\mu {\delta }^2}{3}\end{array}$$

Since $\log (1-x)\ge \frac{x^2/2-x}{1-x}$, then

$$\begin{array}{rl}\log p_2& \le \mu \left(-\delta -\frac{(1-\delta )\cdot ({\delta }^2/2-\delta )}{1-\delta }\right)\\ & \le \mu \left(-\delta -{\delta }^2/2+\delta \right)\\ & =-\frac{\mu {\delta }^2}{2}\end{array}$$

Finally

$$\begin{array}{rl}\mathbb{P}\{|S_N-\mu |\ge \delta \mu \}& \le p_1+p_2\\ & \le e^{-\mu {\delta }^2/3}+e^{-\mu {\delta }^2/2}\\ & \le 2e^{-\mu {\delta }^2/3}\square \end{array}$$

Chernoff’s inequality: Additive form

Let $X_i$ be $N$ independent Bernoulli random variables with parameters $p_i$. Let $S_N=X_1+\cdots +X_N\in \left[a,b\right]$, with mean $\mu =\mathbb{E}{S}_N$.

Then, for every $\epsilon >0$ we have

$$\mathbb{P}\{S_N\ge \mu +\epsilon \}=\mathbb{P}\{S_N\le \mu -\epsilon \}\le e^{-2{\epsilon }^2/(N(b-a{)}^2)}$$

In the special case where $X_i\in \{0,1\}$, i.e. $a=0$ and $b=1$, we have

$$\mathbb{P}\{S_N\ge \mu +\epsilon \}=\mathbb{P}\{S_N\le \mu -\epsilon \}\le e^{-2{\epsilon }^2/N}$$

---

Hoeffding’s inequality

Let $X_1,...,X_N$ be independent symmetric Bernoulli random variables, i.e., random binary random variables that assumes value $1$ or $-1$ with probability $1/2$. Let $a=(a_1,\dots ,a_N)\in {\mathbb{R}}^N$. Then, for every $t\ge 0$, we have

$$\mathbb{P}\left\{\sum _{i=1}^N{a}_i{X}_i\ge t\right\}\le \exp \left(-\frac{t^2}{2\Vert a{\Vert }_2^2}\right).$$

Proof

We start multiplying both sides of the inequality by a value $\lambda >0$ and and exponentiate them (as for the proof of Chebyshev’s inequality), and then we apply Markov’s inequality.

$$\begin{array}{rl}\mathbb{P}\left\{\sum _{i=1}^N{a}_i{X}_i\ge t\right\}& =\mathbb{P}\left\{\exp \left(\lambda \sum _{i=1}^N{a}_i{X}_i\right)\ge \exp (\lambda t)\right\}\\ & \le \frac{\mathbb{E}\exp \left(\lambda {\sum }_{i=1}^N{a}_i{X}_i\right)}{e^{\lambda t}}\\ & =e^{-\lambda t}\mathbb{E}\prod _{i=1}^N{e}^{\lambda a_i{X}_i}\\ & =e^{-\lambda t}\prod _{i=1}^N\mathbb{E}{e}^{\lambda a_i{X}_i}\end{array}$$

where the last inequality holds by the indipendence of the random variables.

For every $i$, since $X_i\in \{-1,1\}$, we have that $\mathbb{E}{e}^{\lambda a_i{X}_i}=\frac{e^{\lambda a_i}+e^{-\lambda a_i}}{2}=\cosh (\lambda a_i)$ (see hyperbolic functions).

In can be prooved (see this) that $\cosh (x)\le e^{x^2/2}$, for every $x\in \mathbb{R}$. Therefore,

$$\prod _{i=1}^N\mathbb{E}{e}^{\lambda a_i{X}_i}\le \prod _{i=1}^N{e}^{{\lambda }^2{a}_i^2/2}=\exp \left(\frac{{\lambda }^2}{2}\sum _{i=1}^N{a}_i^2\right)=\exp \left(\frac{{\lambda }^2}{2}\Vert a{\Vert }_2^2\right)$$

By combining the previous inequality we have

$$\mathbb{P}\left\{\sum _{i=1}^N{a}_i{X}_i\ge t\right\}\le \exp \left(-\lambda t+\frac{{\lambda }^2}{2}\Vert a{\Vert }_2^2\right)$$

for every $\lambda \ge 0$.

Since the $\exp$ function is convex, we can minimize it simply by finding the value of $\lambda$ such that the derivative is $0$ (thus providing a better upper bound). The derivative is $-t+\lambda \Vert a{\Vert }_2^2$, and it’s equal to $0$ when $\lambda =t/\Vert a{\Vert }_2^2$. Therefore,

$$\mathbb{P}\left\{\sum _{i=1}^N{a}_i{X}_i\ge t\right\}\le \exp \left(-\frac{t^2}{\Vert a{\Vert }_2^2}+\frac{1}{2}\frac{t^2}{\Vert a{\Vert }_2^2}\right)=\exp \left(-\frac{t^2}{2\Vert a{\Vert }_2^2}\right).\square$$

Hoeffding’s inequality, two-sided

Let $X_1,...,X_N$ be independent symmetric Bernoulli random variables, i.e., random binary random variables that assumes value $1$ or $-1$ with probability $1/2$. Let $a=(a_1,\dots ,a_N)\in {\mathbb{R}}^N$. Then, for every $t\ge 0$, we have

$$\mathbb{P}\left\{\left|\sum _{i=1}^N{a}_i{X}_i\right|\ge t\right\}\le 2\exp \left(-\frac{t^2}{2\Vert a{\Vert }_2^2}\right).$$

Proof

Let $S_N={\sum }_{i=1}^N{a}_i{X}_i$. We can simply apply the Hoeffding’s inequality for the variables $-X_i$ instead of $X_i$, and obtain the same bound for $\mathbb{P}\{-S_N\ge t\}$. Then

$$\mathbb{P}\{|S_N|\ge t\}=\mathbb{P}\{S_N\ge t\}+\mathbb{P}\{-S_N\ge t\}.\square$$