不等式

sup inf 不等式

inf⁡A=−sup⁡(−A)\inf A = -\sup(-A)

∣sup⁡Af−sup⁡Ag∣≤sup⁡A∣f−g∣,∣inf⁡Af−inf⁡Ag∣≤sup⁡A∣f−g∣.\left|\sup_Af-\sup_Ag\right|\leq\sup_A|f-g|,\quad\left|\inf_Af-\inf_Ag\right|\leq\sup_A|f-g|.

概率

Markov’s Inequality

Markov’s inequality - Wikipedia

Suppose XX is a nonnegative random variable and a>0a>0, then,

P(X≥a)≤E[X]aP(X\geq a)\leq \frac{\mathbb E[X]}{a}

Chernoff Bound

Chernoff bound - Wikipedia

Suppose X1,⋯ ,XnX_1,\cdots,X_n are independent random variables taking values in {0,1}\{0,1\}. Let X=∑i=1nXiX=\sum_{i=1}^nX_i and μ=E[X]\mu=\mathbb E[X]. Then for any δ>0\delta>0,

P(X≥(1+δ)μ)≤(eδ(1+δ)1+δ)μ,P(X≤(1+δ)μ)≤(e−δ(1+δ)1+δ)μ.\begin{gather*} P\left(X\geq(1+\delta)\mu\right)\leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu,\\ P\left(X\leq(1+\delta)\mu\right)\leq \left(\frac{e^{-\delta}}{(1+\delta)^{1+\delta}}\right)^\mu. \end{gather*}

For any δ∈(0,1)\delta\in(0,1),

P(∣X−μ∣≥δμ)≤2e−δ2μ/3P(\left|X-\mu\right|\geq \delta\mu)\leq 2e^{-\delta^2\mu/3}

代数

Cauchy-Schwarz

(∑i=1naibi)2≤(∑i=1nai2)(∑i=1nbi2)\left(\sum_{i=1}^na_ib_i\right)^2\leq\left(\sum_{i=1}^na_i^2\right)\left(\sum_{i=1}^nb_i^2\right)

幂平均不等式

Mp(x1,⋯ ,xn)=(1n∑i=1nxip)1pM_p(x_1,\cdots,x_n)=\left(\frac{1}{n}\sum_{i=1}^nx_i^p\right)^{\frac{1}{p}}

Mp(x1,…,xn)≤Mq(x1,…,xn)if p<qM_p(x_1,\dots,x_n)\le M_q(x_1,\dots,x_n)\quad\text{if}~p<q

取p=1,q>1p=1,q>1

1n∑i=1nxi≤(1n∑i=1nxik)1k(1n∑i=1nxi)k≤1n∑i=1nxik(∑i=1nxi)k≤nk−1∑i=1nxik\begin{gather*} \frac1n\sum_{i=1}^nx_i\leq\left(\frac1n\sum_{i=1}^nx_i^k\right)^{\frac1k}\\ \left(\frac1n\sum_{i=1}^nx_i\right)^k\leq \frac1n\sum_{i=1}^nx_i^k\\ \left(\sum_{i=1}^n x_i\right)^k \leq n^{k-1}\sum_{i=1}^nx_i^k \end{gather*}

(∑i=1nxi)k≥∑i=1nxik\left(\sum_{i=1}^n x_i\right)^k\geq \sum_{i=1}^n x_i^k

定理

中值定理

ff在[a,b][a,b]连续，在(a,b)(a,b)可微，则存在一点a<c<ba<c<b，使得

f′(c)=f(b)−f(a)b−af^\prime(c) = \frac{f(b)-f(a)}{b-a}

中值定理 - 维基百科，自由的百科全书

Envolope Theorem (包络定理)

假设f(x,α)f(\mathbf x,\boldsymbol \alpha)是Rn+l\mathbb R^{n+l}上的可微实函数，其中x∈Rn\mathbf x\in\mathbb R^n为自变量，α∈Rl\boldsymbol \alpha\in\mathbb R^{l}为参数，目标是选择适当的x\mathbf x以最大化/最小化ff。设V(α)=f(x∗,α)V(\boldsymbol\alpha)=f(\mathbf x^*,\boldsymbol \alpha)，其中x∗\mathbf x^*为ff取最大值/最小值时的x\mathbf x，则有

dVdα=∂f∂α∣x=x∗\frac{\text{d}V}{\text d\boldsymbol \alpha} = \left.\frac{\partial f}{\partial \boldsymbol \alpha}\right|_{\mathbf x=\mathbf x^*}

包络定理 - 维基百科，自由的百科全书

假设f(x,θ)f(\mathbf x,\boldsymbol\theta)关于θ\boldsymbol \theta连续可微，则

v(θ)=sup⁡x∈Gf(x,θ)v(\boldsymbol \theta) = \sup_{\mathbf x\in G}f(\mathbf x,\boldsymbol\theta)

在x∗\mathbf x^*为单值解处可微，且其导数满足Dθv[θ]=Dθf[x(θ),θ]D_{\boldsymbol \theta}v[\theta]=D_{\boldsymbol \theta}f[\mathbf x(\boldsymbol \theta),\boldsymbol \theta]