Introduction

這篇主要講述用大致估計的方式找出期望值 (類似數學中的測度論)

Probability Inequalities

基礎公式

以下會介紹這幾個定理 :

• Markov's inequality
• Chebyshev's inequality (
  $\text{color}red\mathrm{超}\mathrm{重}\mathrm{要}$)
• Hoeffding's inequality
• Bernoulli 的情況

---

Markov's inequality

$X$ 是 non-negative random variable
且

$\mathbb{E}(X)$ exist
這時

$\text{color}blue\underset{\mathrm{此}\mathrm{分}\mathrm{布}\mathrm{的}\mathrm{右}\mathrm{尾}\mathrm{有}\mathrm{多}\mathrm{厚}}{\underbrace{P(X>t)}}\le \frac{\mathbb{E}(X)}{t}$

證明過程如下 :

$\begin{array}{r}EX={\int }_0^{\mathrm{\infty }}xf(x)dx=[{\int }_0^{t}xf(x)dx+{\int }_t^{\mathrm{\infty }}xf(x)dx]\ge {\int }_t^{\mathrm{\infty }}xf(x)dx\ge {\int }_t^{\mathrm{\infty }}tf(x)dx=tP(x>t)\end{array}$

$\Rightarrow P(x>t)\le \frac{EX}{t}$

小舉例 :
全班平均

$50$ 分，求

$90$ 分以上的比例 :

$P(X>90)\le \frac{50}{90}=\frac{5}{9}$

---

Chebyshev's inequality

先令

$\mu =\mathbb{E}(X),{\sigma }^2=\mathbb{V}(X)$
這時

$\text{color}blue\mathbb{P}(|X-\mu |\ge t)\le \frac{{\sigma }^2}{t^2},\text{and }\mathbb{P}(|Z\ge k|)\le \frac{1}{k^2},\text{for }Z=\frac{(X-\mu )}{\sigma }$

證明過程如下 :

$P(|X-\mu |\ge t)=\underset{\text{color}orangeP(x>t)\le \frac{EX}{t}}{\underbrace{P(|X-\mu {|}^2\ge t^2)}}\le \frac{E(X-mu{)}^2}{t^2}=\frac{{\sigma }^2}{t^2}$

$P(|\frac{(X-\mu )}{\sigma }\ge K|)=P(|X-\mu |\ge \sigma K)\le \frac{{\sigma }^2}{(\sigma k{)}^2}=\frac{1}{k^2}$

小舉例-1 :
全班平均

$50$ 分，標準差

$10$ 分，求

$90$ 分以上的比例 :

$P(X>90)\approx \frac{1}{2}P(|X-50|>40)\le \frac{1}{2}\times \frac{100}{1600}=\frac{1}{32}$

小舉例-2 :
全班平均

$50$ 分，標準差

$30$ 分，求

$90$ 分以上的比例 :

$P(X>90)\approx \frac{1}{2}P(|X-50|>40)\le \frac{1}{2}\times \frac{900}{1600}=\frac{9}{32}$

$\Rightarrow$ 可以從小舉例當中看到當

${\sigma }^2$ 很大，或是

$t$ 很小的時候，估計出來的值就會失去意義

---

Hoeffding's inequality

先令

$Y_1,...,Y_n$ 為 random variables，並且

$\mathbb{E}(Y_i)=0,a_i\le Y_i\le b_i$
這時令

$ϵ>0,\text{for any }t>0$

$\text{color}blue\mathbb{P}({\mathrm{\Sigma }}_{i=1}^n{Y}_i\ge ϵ)\le e^{-tϵ}\cdot {\mathrm{\Pi }}_{i=1}^n{e}^{t^2(b_i-a_i{)}^2/8}$

---

Bernoulli 的情況

先令

$X_1,...,X_n\sim Bernoulli(p)$
這時對於所有

$ϵ>0$

$\mathbb{P}(|\overline{X_n}-p|>ϵ)\le 2e^{-2n{ϵ}^2},\text{for }\overline{X_n}=n^{-1}{\mathrm{\Sigma }}_{i=1}^n{X}_i$

Examples

Question 1 (estimating a proportion–估計母體的

$p$)

question :

$Y_i$ 是第

$i$ 個樣本的狀態(

$1,0$)，

$i=1,...,n$，且

$Y_i\stackrel{iid}{\sim }Bernoulli(p)$，求出母體的

$p$
(給定

$ϵ=0.1,n=100$)

solution :
我們可以先從題目得知 :

$\{\begin{array}{l}E(Y_i)=p\\ V(Y_i)=p(1-p)\end{array}$
並且可以知道題目想要用

$\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i\stackrel{\mathrm{估}\mathrm{計}}{⟶}p$，也就是在樣本

$n$ 人中狀態為

$1$ 的比例
簡化成數學式 :

$P(|\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i-p|>ϵ)$
然後可以知道這個式子的平均跟變異數 :

$\{\begin{array}{l}E(\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i)=p\\ V(\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i)=\frac{1}{n^2}{\mathrm{\Sigma }}_{i=1}^{n}V(Y_i)=\frac{p(1-p)}{n}\end{array}$

$(i)$ Chebyshev's inequality :

$P(|\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i-p|>ϵ)\le \underset{\mathrm{就}\mathrm{是}\frac{{\sigma }^2}{t^2}，{\sigma }^2=\mathrm{上}\mathrm{述}\mathrm{的}V，t=\mathrm{上}\mathrm{述}\mathrm{的}ϵ}{\underbrace{\frac{p(1-p)}{{ϵ}^{2}n}}}\le \frac{0.5\times (1-0.5)}{0.1\times 0.1\times 100}$

$(ii)$ Hoeffding's inequality :

$P(|\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i-p|>ϵ)\le 2e^{-2\times 100\times \frac{1}{100}}=e^{-2}$

$(iii)$ CLT(central limit theorem)

$(ϵ=0.2)$ :

$P(|\frac{1}{n}{\mathrm{\Sigma }}_{i=1}^n{Y}_i-p|>ϵ)\approx 3.17\times {10}^{-5}$

Inequalities for Expectations

基礎公式

以下會介紹這幾個定理 :

• Cauchy-Schwartz inequality
• Jensen's inequality

---

Cauchy-Schwartz inequality

當

$X$ 跟

$Y$ 的變異數都是有限的時候

$|(\mathbb{E}|XY)|\le \sqrt{\mathbb{E}(X^2)\mathbb{E}(Y^2)}$

$\Rightarrow E(X-{\mu }_X)(Y-{\mu }_Y)\le \sqrt{E(X-{\mu }_X{)}^2(Y-{\mu }_Y{)}^2}=\sqrt{(VX)(VY)}$

$\Rightarrow |\frac{cov(X,Y)}{\sqrt{(VX)(VY)}}|=|P(X,Y)|\le 1$
這條公式是從

$|\overrightarrow{x}\cdot \overrightarrow{y}|\le |\overrightarrow{x}|\cdot |\overrightarrow{y}|$ 推導而來

證明如下 :

$\overline{xy}=\frac{1}{n}(\overrightarrow{x}\cdot \overrightarrow{y})$

$\overline{x^2}=\frac{1}{n}|\overrightarrow{x}{|}^2$

$\overline{y^2}=\frac{1}{n}|\overrightarrow{y}{|}^2$
所以藉由原始公式 :

$|\overrightarrow{x}\cdot \overrightarrow{y}|=\overline{xy}\le |\overrightarrow{x}|\cdot |\overrightarrow{y}|=\sqrt{\overline{x^2}}\cdot \sqrt{\overline{y^2}}$
也就是說

$XY\text{的 sample mean}\le \sqrt{X^2\text{的 sample mean}}\sqrt{Y^2\text{的 sample mean}}$

---

Jensen's inequality

主要使用在函數不是線性的時候
簡單來說就是用微積分的概念來看，觀察函數是 convex 還是 concave

convex :

$\mathbb{E}(g(X))\ge g(\mathbb{E}(X))$
代表從中間隨便畫出一條線，線上的中點(A點)會比投影到這個函數的值(B點)還要大

concave :

$\mathbb{E}(g(X))\le g(\mathbb{E}(X))$
跟 convex 相反