Prob and Tail Bounds

机会约束的概率形式为
$$Prob[\sum _{i=1}^n{z}_i{U}_i\ge t]\le \epsilon$$
其中，$U_i$是随机变量，$z_i$为固定参数. 可以使用很多方法来控制概率，其中一些tail bounds的方法证明是有有效的.
最简单的tail bound是Markov inequality，即对于非负的随机变量$U$和$a\ge 0$
$$Prob(U\ge a)\le \frac{\mathbb{E}[U]}{a}$$
根据此可以推出Chebyshev bound
$$Prob(U>\mathbb{E}U+t)\le Prob((U-\mathbb{E}U{)}^2\ge t^2)\le \frac{\mathbb{E}(U-\mathbb{E}U{)}^2}{t^2}$$
为了描述极端低概率事件的bounds，一种常用的技术是chernoff bound.
$$Prob(U\ge t)=Prob(e^{\lambda U}\ge e^{\lambda U})\le \frac{\mathbb{E}{e}^{\lambda U}}{e^{\lambda t}}$$
或者等价的
$$Prob(U\ge t)\le \underset{\lambda \ge 0}{\inf }\mathbb{E}{e}^{\lambda U}{e}^{-\lambda U}$$

Examples

example 1

令$Z$为一个零均值高斯随机变量，方差为${\sigma }^2$
$$\mathbb{E}\exp (\lambda Z)=\exp (\frac{{\lambda }^2{\sigma }^2}{2})$$
并且对于$t\ge 0$
$$Prob(Z\ge t)\le \underset{\lambda \ge 0}{\inf }\exp (\frac{{\lambda }^2{\sigma }^2}{2}-\lambda t)=\exp (-\frac{t^2}{2{\sigma }^2})$$

Whenever there is a parameter $\sigma \ge 0$ such that a mean-zero random variable satisfies
$$\mathbb{E}{e}^{\lambda U}\le \exp (\frac{{\lambda }^2{\sigma }^2}{2})$$
we call the random variable sub-Gaussian with parameter ${\sigma }^2$, this is an extremely useful concept.

example 2

Indeed, we have Hoeffding’ s inequality which gives sharp bounds on sums of sub-Gaussian random variables.

令$U_1,U_2,\dots ,U_n$为独立的mean-zero sub Gaussian random variables参数为$\sigma =({\sigma }_1,\dots ,{\sigma }_n)$
$$Prob(\sum _{i=1}^n{U}_i\ge t)\le \exp (-\frac{t^2}{2\Vert \sigma {\Vert }_2^2})$$
使用Chernoff bound，令$Z=1^{T}U$，可以得到
$$Prob(Z\ge t)\le \exp (\frac{{\lambda }^2{\sum }_{i=1}^n{\sigma }_i^2}{2}-\lambda t)$$
在$\lambda \ge 0$区间最小化可以得到tail bound.

example 3

Bound random variables(Hoeffding’s lemma) 令$U\in [a,b]$为一个mean-zero random variable，对于$a\le 0\le b$，$U$是一个sub-Gaussian，并且
$$\mathbb{E}[\exp (\lambda U)]\le \exp (\frac{{\lambda }^2(b-a{)}^2}{8})$$
Proof:
由之前的方程可以得到
$$Prob(\sum _{t=1}^n{U}_i\ge t)\le \exp (-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2})$$
由指数函数的凸性可以得到
$$e^{\lambda x}\le e^{\lambda a}\frac{b-x}{b-a}+e^{\lambda b}\frac{x-a}{b-a}$$
关于随机变量$U$取期望，可以得到
$$\mathbb{E}[e^{\lambda U}]\le \frac{b}{b-a}{e}^{\lambda a}+\frac{-a}{b-a}{e}^{\lambda b}$$
令$z=\lambda (b-a),p=\frac{b}{b-a}，pz=\lambda b$且$(1-p)z=-\lambda a$所以
$$\mathbb{E}[e^{\lambda U}]\le p^{\lambda a}+(1-p)e^{\lambda b}=e^{(p-1)z}[p+(1-p)e^z]$$
令$f(z)=(p-1)z+\log (p+(1-p)e^z)$，求出一阶导数和二阶导数得到
$$\{\begin{array}{l}{f}^{\prime }(z)=(p-1)+\frac{1-p}{p{e}^{-z}+1-p}\\ f^{\prime \prime }(z)=\frac{p(1-p)e^{-z}}{(p{e}^{-z}+1-p{)}^2}\le \frac{1}{4}\end{array}$$
且可以计算出$f(0)=0,f^{\prime }(0)=0$，根据Taylor公式可以得到$f(z)\le \frac{1}{8}{z}^2$，当$b=-a$时，可以得到以下简单的证明
$$\mathbb{E}[e^{\lambda U}]\le \frac{b}{2b}{e}^{-\lambda b}+\frac{b}{2b}{e}^{\lambda b}=\sum _{k\in {\mathbb{Z}}_{+}}\frac{{\lambda }^k{b}^k}{k!}=1+\sum _{k\ge 1}\frac{{\lambda }^{2k}{b}^{2k}}{(2k)!}\le 1+\sum _{k\ge 1}(\frac{\lambda b}{2}{)}^2\frac{1}{k!}=\exp (\frac{{\lambda }^2{b}^2}{2})$$

最后

以上就是腼腆白云为你收集整理的【OR】Robust Optimization(8): Probability and tail boundsProb and Tail BoundsExamples的全部内容，希望文章能够帮你解决【OR】Robust Optimization(8): Probability and tail boundsProb and Tail BoundsExamples所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。