概率论-集中不等式

从维基百科和机器学习的书上整理、复制、粘贴了几个常见的集中不等式

• Markov’s inequality
  • statement
  • intuition
  • proof
  • corollaries
• Chebyshev’s inequality
  • statement
  • proof
• Hoeffding’s inequality
  • Hoeffding’s lemma
    • statement
    • Proof
  • proof
• McDiarmid’s inequality
  • statement
  • Definition Martingale Difference
  • Lemma
  • Theorem Azuma’s inequality
    • proof
  • proof

Markov’s inequality

statement

If $X$ is a nonnegative random variable and $a>0$, then the probability that $X$ is at least $a$ is at most the expectation of $X$ divided by $a$

$$\mathrm{P}(X\ge a)\le \frac{\mathrm{E}(X)}{a}$$

intuition

$\mathrm{E}(X)=\mathrm{P}(X<a)\cdot \mathrm{E}(X\mid X<a)+\mathrm{P}(X\ge a)\cdot \mathrm{E}(X\mid X\ge a)$

$\mathrm{E}(X)\ge \mathrm{P}(X\ge a)\cdot \mathrm{E}(X\mid X\ge a)\ge a\cdot \mathrm{P}(X\ge a)$

$\mathrm{P}(X\ge a)\le \frac{\mathrm{E}(X)}{a}$

proof

For any event $E$, let $I_E$ be the indicator random variable of $E$, that is, $I_E=1$ if $E$ occurs and $I_E=0$ otherwise.
Using this notation, we have $I_{(X\ge a)}=1$ if the event $X\ge a$ occurs, and $I_{(X\ge a)}=0$ if $X<a$. Then, given $a>0$,

$$a{I}_{(X\ge a)}\le X$$

which is clear if we consider the two possible values of $X\ge a$. If $X<a$, then $I_{(X\ge a)}=0$, and so $a{I}_{(X\ge a)}=0\le X$.
Otherwise, we have $X\ge a$, for which $I_{X\ge a}=1$ and so $a{I}_{X\ge a}=a\le X$.
Since $\mathrm{E}$ is a monotonically increasing function, taking expectation of both sides of an inequality cannot reverse it. Therefore,

$$\mathrm{E}\left(a{I}_{(X\ge a)}\right)\le \mathrm{E}(X).$$

Now, using linearity of expectations, the left side of this inequality is the same as

$$a\mathrm{E}\left(I_{(X\ge a)}\right)=a(1\cdot \mathrm{P}(X\ge a)+0\cdot \mathrm{P}(X<a))=a\mathrm{P}(X\ge a).$$

Thus we have

$$a\mathrm{P}(X\ge a)\le \mathrm{E}(X)$$

and since $a>0$, we can divide both sides by $a$.

corollaries

$\varphi$ is a nondecreasing nonnegative fundction

$$\mathrm{P}(|X|\ge a)=\mathrm{P}(\phi (|X|)\ge \phi (a))\stackrel{\mathrm{MI}}{\le }\frac{\mathrm{E}(\phi (|X|))}{\phi (a)}$$

Chebyshev’s inequality

statement

$$\mathrm{P}(|X-\mathrm{E}(X)|\ge a)\le \frac{\mathrm{Var}(X)}{a^2},$$

proof

for any $a>0$

$$\mathrm{Var}(X)=\mathrm{E}\left[(X-\mathrm{E}(X){)}^2\right].$$

because Markov’s inequality

$$\mathrm{P}\left((X-\mathrm{E}(X){)}^2\ge a^2\right)\le \frac{\mathrm{Var}(X)}{a^2}.$$

This argument can be summarized (where “MI” indicates use of Markov’s inequality):

$$\mathrm{P}(|X-\mathrm{E}(X)|\ge a)=\mathrm{P}\left((X-\mathrm{E}(X){)}^2\ge a^2\right)\stackrel{\mathrm{MI}}{\le }\frac{\mathrm{E}\left((X-\mathrm{E}(X){)}^2\right)}{a^2}=\frac{\mathrm{Var}(X)}{a^2}.$$

Hoeffding’s inequality

Let $X_1,\dots ,X_m$ be independent random variables with $X_i$ taking values in $\left[a_i,b_i\right]$ for all $i\in [1,m]$. Then for any $ϵ>0$, the following inequalities hold for $S_m={\sum }_{i=1}^m{X}_i$ :

$$\begin{array}{c}\mathrm{Pr}\left[S_m-\mathrm{E}\left[S_m\right]\ge ϵ\right]\le e^{-2{ϵ}^2/{\sum }_{i=1}^m{\left(b_i-a_i\right)}^2}\\ \mathrm{Pr}\left[S_m-\mathrm{E}\left[S_m\right]\le -ϵ\right]\le e^{-2{ϵ}^2/{\sum }_{i=1}^m{\left(b_i-a_i\right)}^2}.\end{array}$$

Hoeffding’s lemma

statement

Let $X$ be a random variable with $E[X]=0$ and $a\le X\le b$ with $b>a$. Then, for any $t>0$, the following inequality holds:

$$\mathrm{E}\left[e^{tX}\right]\le e^{\frac{t^2(b-a{)}^2}{8}}.$$

Proof

By the convexity of $x\mapsto e^x$, for all $x\in [a,b]$, the following holds:

$$e^{tx}\le \frac{b-x}{b-a}{e}^{ta}+\frac{x-a}{b-a}{e}^{tb}.$$

Thus, using $\mathrm{E}[X]=0$,

$$\mathrm{E}\left[e^{tX}\right]\le \mathrm{E}\left[\frac{b-X}{b-a}{e}^{ta}+\frac{X-a}{b-a}{e}^{tb}\right]=\frac{b}{b-a}{e}^{ta}+\frac{-a}{b-a}{e}^{tb}=e^{\varphi (t)},$$

where,

$$\varphi (t)=\log \left(\frac{b}{b-a}{e}^{ta}+\frac{-a}{b-a}{e}^{tb}\right)=ta+\log \left(\frac{b}{b-a}+\frac{-a}{b-a}{e}^{t(b-a)}\right).$$

For any $t>0$, the first and second derivative of $\varphi$ are given below:

$$\begin{array}{rl}{\varphi }^{\prime }(t)& =a-\frac{a{e}^{t(b-a)}}{\frac{b}{b-a}-\frac{a}{b-a}{e}^{t(b-a)}}=a-\frac{a}{\frac{b}{b-a}{e}^{-t(b-a)}-\frac{a}{b-a}},\\ {\varphi }^{\prime \prime }(t)& =\frac{-ab{e}^{-t(b-a)}}{{\left[\frac{b}{b-a}{e}^{-t(b-a)}-\frac{a}{b-a}\right]}^2}\\ & =\frac{\alpha (1-\alpha )e^{-t(b-a)}(b-a{)}^2}{{\left[(1-\alpha )e^{-t(b-a)}+\alpha \right]}^2}\\ & =\frac{\alpha }{\left[(1-\alpha )e^{-t(b-a)}+\alpha \right]}\frac{(1-\alpha )e^{-t(b-a)}}{\left[(1-\alpha )e^{-t(b-a)}+\alpha \right]}(b-a{)}^2.\end{array}$$

where $\alpha$ denotes $\frac{-a}{b-a}$. Note that $\varphi (0)={\varphi }^{\prime }(0)=0$ and that ${\varphi }^{\prime \prime }(t)=u(1-u)(b-a{)}^2$ where $u=\frac{\alpha }{\left[(1-\alpha )e^{-t(b-a)}+\alpha \right]}$. Since $u$ is in $[0,1],u(1-u)$ is upper bounded by $1/4$ and ${\varphi }^{\prime }(t)\le \frac{(b-a{)}^2}{4}$. Thus, by the second order expansion of function $\varphi$, there exists $\theta \in [0,t]$ such that:

$$\varphi (t)=\varphi (0)+t{\varphi }^{\prime }(0)+\frac{t^2}{2}{\varphi }^{\prime \prime }(\theta )\le t^2\frac{(b-a{)}^2}{8},$$

proof

$\begin{array}{rl}\mathrm{Pr}\left[S_m-\mathrm{E}\left[S_m\right]\ge ϵ\right]& \le e^{-tϵ}\mathrm{E}\left[e^{t\left(S_m-\mathrm{E}\left[S_m\right]\right)}\right]\\ & ={\Pi }_{i=1}^m{e}^{-tϵ}\mathrm{E}\left[e^{t\left(X_i-\mathrm{E}\left[X_i\right]\right)}\right]\\ & \le {\Pi }_{i=1}^m{e}^{-tϵ}{e}^{t^2{\left(b_i-a_i\right)}^2/8}\\ & =e^{-tϵ}{e}^{t^2{\sum }_{i=1}^m{\left(b_i-a_i\right)}^2/8}\\ & \le e^{-2{ϵ}^2/{\sum }_{i=1}^m{\left(b_i-a_i\right)}^2},\end{array}$

McDiarmid’s inequality

statement

Let $X_1,\dots ,X_m\in {\mathcal{X}}^m$ be a set of $m\ge 1$ independent random variables and assume that there exist $c_1,\dots ,c_m>0$ such that $f:{\mathcal{X}}^m\to \mathbb{R}$ satisfies the following conditions:

$$\left|f\left(x_1,\dots ,x_i,\dots ,x_m\right)-f\left(x_1,\dots ,x_i^{\prime },\dots x_m\right)\right|\le c_i,$$

for all $i\in [1,m]$ and any points $x_1,\dots ,x_m,x_i^{\prime }\in \mathcal{X}$. Let $f(S)$ denote $f\left(X_1,\dots ,X_m\right)$, then, for all $ϵ>0$, the following inequalities hold:

$$\begin{array}{c}\mathrm{Pr}[f(S)-\mathrm{E}[f(S)]\ge ϵ]\le \exp \left(\frac{-2{ϵ}^2}{{\sum }_{i=1}^m{c}_i^2}\right)\\ \mathrm{Pr}[f(S)-\mathrm{E}[f(S)]\le -ϵ]\le \exp \left(\frac{-2{ϵ}^2}{{\sum }_{i=1}^m{c}_i^2}\right).\end{array}$$

Definition Martingale Difference

A sequence of random variables $V_1,V_2,\dots$ is a martingale difference sequence with respect to $X_1,X_2,\dots$ if for all $i>0,V_i$ is a function of $X_1,\dots ,X_i$ and

$$\mathrm{E}\left[V_{i+1}\mid X_1,\dots ,X_i\right]=0.$$

Lemma

Let $V$ and $Z$ be random variables satisfying $\mathrm{E}[V\mid Z]=0$ and, for some function $f$ and constant $c\ge 0$, the inequalities:

$$f(Z)\le V\le f(Z)+c.$$

Then, for all $t>0$, the following upper bound holds:

$$\mathrm{E}\left[e^{tV}\mid Z\right]\le e^{t^2{c}^2/8}.$$

Theorem Azuma’s inequality

Let $V_1,V_2,\dots$ be a martingale difference sequence with respect to the random variables $X_1,X_2,\dots$, and assume that for all $i>0$ there is a constant $c_i\ge 0$ and
random variable $Z_i$, which is a function of $X_1,\dots ,X_{i-1}$, that satisfy

$$Z_i\le V_i\le Z_i+c_i.$$

Then, for all $ϵ>0$ and $m$, the following inequalities hold:

$$\begin{array}{c}\mathrm{Pr}\left[\sum _{i=1}^m{V}_i\ge ϵ\right]\le \exp \left(\frac{-2{ϵ}^2}{{\sum }_{i=1}^m{c}_i^2}\right)\\ \mathrm{Pr}\left[\sum _{i=1}^m{V}_i\le -ϵ\right]\le \exp \left(\frac{-2{ϵ}^2}{{\sum }_{i=1}^m{c}_i^2}\right).\end{array}$$

proof

Proof For any $k\in [1,m]$, let $S_k={\sum }_{i=1}^k{V}_k$. Then, using Chernoff’s bounding technique, for any $t>0$, we can write

$$\begin{array}{rl}\mathrm{Pr}\left[S_m\ge ϵ\right]& \le e^{-tϵ}\mathrm{E}\left[e^{t{S}_m}\right]\\ & =e^{-tϵ}\mathrm{E}\left[e^{t{S}_{m-1}}\mathrm{E}\left[e^{t{\mathbf{V}}_m}\mid X_1,\dots ,X_{m-1}\right]\right]\\ & \le e^{-tϵ}\mathrm{E}\left[e^{t{S}_{m-1}}\right]e^{t^2{c}_m^2/8}\\ & \le e^{-tϵ}{e}^{t^2{\sum }_{i=1}^m{c}_i^2/8}\\ & =e^{-2{ϵ}^2/{\sum }_{i=1}^m{c}_i^2}\end{array}$$

where we chose $t=4ϵ/{\sum }_{i=1}^m{c}_i^2$ to minimize the upper bound. This proves the first statement of the theorem, and the second statement is shown in a similar way.
($ifF1\subset F2,thenE[E[Y|F1]|F2]=E[E[Y|F2]|F1]=E[Y|F1]$)

proof

Define a sequence of random variables $V_k,k\in [1,m]$, as follows: $V=f(S)-\mathrm{E}[f(S)],V_1=\mathrm{E}\left[V\mid X_1\right]-\mathrm{E}[V]$, and for $k>1$,

$$V_k=\mathrm{E}\left[V\mid X_1,\dots ,X_k\right]-\mathrm{E}\left[V\mid X_1,\dots ,X_{k-1}\right].$$

Note that $V={\sum }_{k=1}^m{V}_k$. Furthermore, the random variable $\mathrm{E}\left[V\mid X_1,\dots ,X_k\right]$ is a function of $X_1,\dots ,X_k$. Conditioning on $X_1,\dots ,X_{k-1}$ and taking its expectation is therefore:

$$\mathrm{E}\left[\mathrm{E}\left[V\mid X_1,\dots ,X_k\right]\mid X_1,\dots ,X_{k-1}\right]=\mathrm{E}\left[V\mid X_1,\dots ,X_{k-1}\right],$$

which implies $\mathrm{E}\left[V_k\mid X_1,\dots ,X_{k-1}\right]=0$. Thus, the sequence ${\left(V_k\right)}_{k\in [1,m]}$ is a martingale difference sequence. Next, observe that, since $\mathrm{E}[f(S)]$ is a scalar, $V_k$ can be expressed as follows:

$$V_k=\mathrm{E}\left[f(S)\mid X_1,\dots ,X_k\right]-\mathrm{E}\left[f(S)\mid X_1,\dots ,X_{k-1}\right].$$

Now define the random variables for each $i$

$$\begin{array}{rl}{U}_i& :=\underset{x\in {\mathcal{X}}_i}{\sup }\mathbb{E}\left[f\left(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)},X_i=x\right]-\left[f\left(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)}\right],\\ L_i& :=\underset{x\in {\mathcal{X}}_i}{\inf }\mathbb{E}\left[f\left(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)},X_i=x\right]-\left[f\left(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)}\right].\end{array}$$

Since $X_i,\dots ,X_n$ are independent of each other, conditioning on $X_i=x$ does not affect the probabilities of the other variables, so these are equal to the expressions

$$\begin{array}{rl}{U}_i& =\underset{x\in {\mathcal{X}}_i}{\sup }\mathbb{E}\left[f\left(X_{1\to (i-1)},x,X_{(i+1)\rightharpoondown n}\right)-f\left(X_{1\rightharpoondown (i-1)},X_{i\to n}\right)\mid X_{1\to (i-1)}\right],\\ L_i& =\underset{x\in {\mathcal{X}}_i}{\inf }\mathbb{E}\left[f\left(X_{1\to (i-1)},x,X_{(i+1)\rightharpoondown n}\right)-f\left(X_{1\to (i-1)},X_{i\rightharpoondown n}\right)\mid X_{1\to (i-1)}\right].\end{array}$$ $$\begin{array}{rl}{U}_i-L_i& =\underset{u\in {\mathcal{X}}_i,\ell \in {\mathcal{X}}_i}{\sup }\mathbb{E}\left[f\left(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)}\right]-\mathbb{E}\left[f\left(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)}\right]\\ & =\underset{u\in {\mathcal{X}}_i,\ell \in {\mathcal{X}}_i}{\sup }\mathbb{E}\left[f\left(X_{1\to (i-1)},u,X_{(i+1)\rightharpoondown n}\right)-f\left(X_{1\to (i-1)},l,X_{(i+1)\rightharpoondown n}\right)\mid X_{1\rightharpoondown (i-1)}\right]\\ & \le \underset{x_u\in {\mathcal{X}}_i,x_l\in {\mathcal{X}}_i}{\sup }\mathbb{E}\left[c_i\mid X_{1\rightharpoondown (i-1)}\right]\\ & \le c_i\end{array}$$

$L_i$ is a random variables about $X_1,X2,...,X_{i-1}$
thus, $L_k\le V_k\le L_k+c_k$. In view of these inequalities, we can apply Azuma’s inequality to $V={\sum }_{k=1}^m{V}_k$