---
# System prepended metadata

title: mathstat_ch4_Inequalities
tags: [mathematic statistics]

---

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



# Probability Inequalities  
## 基礎公式  
以下會介紹這幾個定理 :  
* **Markov's inequality**  
* **Chebyshev's inequality** ($\color{red}{超重要}$)  
* **Hoeffding's inequality**  
* **Bernoulli 的情況**

---

### Markov's inequality  
$X$ 是 non-negative random variable  
且 $\mathbb{E}(X)$ exist  
這時 $\color{blue}{\underbrace{P(X>t)}_{此分布的右尾有多厚} \le \cfrac{\mathbb{E}(X)}{t}}$  

證明過程如下 :  
:::spoiler  
$\begin{split} EX = \int^{\infty}_{0} xf(x) \ dx = \left[ \ \int^{t}_{0} xf(x) \ dx + \int^{\infty}_{t} xf(x) \ dx \ \right]  \ge \int^{\infty}_{t} xf(x) \ dx \ge \int^{\infty}_{t} tf(x) \ dx = tP(x > t) \end{split}$  
$\Rightarrow P(x > t) \le \cfrac{EX}{t}$  
:::  

<br>

小舉例 :  
全班平均 $50$ 分，求 $90$ 分以上的比例 :  
$P(X > 90) \le \cfrac{50}{90} = \cfrac{5}{9}$  

---

### Chebyshev's inequality  
先令 $\mu = \mathbb{E}(X),\ \sigma^2 = \mathbb{V}(X)$  
這時 $\color{blue}{\mathbb{P}(|X-\mu| \ge t) \le \cfrac{\sigma^2}{t^2},\ \text{and } \mathbb{P}(|Z \ge k|) \le \cfrac{1}{k^2},\ \text{for } Z = \cfrac{(X - \mu)}{\sigma}}$  

證明過程如下 :  
:::spoiler  
$P(|X-\mu| \ge t) = \underbrace{P(|X-\mu|^2 \ge t^2)}_{\color{orange}{P(x > t) \le \frac{EX}{t}}} \le \cfrac{E(X - mu)^2}{t^2} = \cfrac{\sigma^2}{t^2}$  

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

<br>

小舉例-1 :  
全班平均 $50$ 分，標準差 $10$ 分，求 $90$ 分以上的比例 :  
$P(X > 90) \approx \cfrac{1}{2}P(|X - 50| > 40) \le \cfrac{1}{2} \times \cfrac{100}{1600} = \cfrac{1}{32}$  

小舉例-2 :  
全班平均 $50$ 分，標準差 $30$ 分，求 $90$ 分以上的比例 :  
$P(X > 90) \approx \cfrac{1}{2}P(|X - 50| > 40) \le \cfrac{1}{2} \times \cfrac{900}{1600} = \cfrac{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$  
這時令 $\epsilon > 0,\ \text{for any } t>0$  
$\color{blue}{\mathbb{P}(\Sigma_{i=1}^{n} \ Y_i \ge \epsilon) \le e^{-t \epsilon} \cdot \Pi_{i=1}^{n} \ e^{t^2 (b_i - a_i)^2/8}}$

---

### Bernoulli 的情況  
先令 $X_1,\ ...,\ X_n \sim Bernoulli(p)$  
這時對於所有 $\epsilon > 0$  
$\mathbb{P}(|\overline{X_n} - p| > \epsilon) \le 2e^{-2n \epsilon^2},\ \text{for } \overline{X_n} = n^{-1} \Sigma_{i=1}^{n}X_i$  


## Examples  
### **Question 1** (estimating a proportion--估計母體的 $p$)  
**question** : $Y_i$ 是第 $i$ 個樣本的狀態($1,\ 0$)，$i = 1,\ ... ,\ n$，且 $Y_i \overset{iid}{\sim} Bernoulli(p)$，求出母體的 $p$  
(給定 $\epsilon = 0.1,\ n = 100$)  

**solution** :  
我們可以先從題目得知 : $\begin{cases} E(Y_i) = p \\ V(Y_i) = p (1-p) \end{cases}$  
並且可以知道題目想要用 $\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i \overset{估計}{\longrightarrow} p$，也就是在樣本 $n$ 人中狀態為 $1$ 的比例  
簡化成數學式 : $P(|\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i - p| > \epsilon)$  
然後可以知道這個式子的平均跟變異數 :  
$\begin{cases} E(\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i) = p \\ V(\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i) = \cfrac{1}{n^2} \Sigma_{i=1}^{n} V(Y_i) = \cfrac{p(1-p)}{n} \end{cases}$  

$(i)$ **Chebyshev's inequality** :  
$P(|\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i - p| > \epsilon) \le \underbrace{\cfrac{p(1-p)}{\epsilon^2 n}}_{就是 \frac{\sigma^2}{t^2}，\sigma^2 = 上述的 V，t = 上述的\epsilon} \le \cfrac{0.5 \times (1-0.5)}{0.1 \times 0.1 \times 100}$  


$(ii)$ **Hoeffding's inequality** :  
$P(|\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i - p| > \epsilon) \le 2 e^{-2 \times 100 \times \frac{1}{100}} = e^{-2}$  


$(iii)$ **CLT(central limit theorem)** $(\epsilon = 0.2)$ :  
$P(|\cfrac{1}{n} \Sigma_{i=1}^{n}Y_i - p| > \epsilon) 
\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 \vert \cfrac{cov(X,\ Y)}{\sqrt{(VX)(VY)}} \vert = |P(X,\ Y)| \le 1$  
這條公式是從 $|\vec{x} \cdot \vec{y}| \le |\vec{x}| \cdot |\vec{y}|$ 推導而來  

證明如下 :  
:::spoiler  
$\overline{xy} = \cfrac{1}{n} (\vec{x} \cdot \vec{y})$  
$\overline{x^2} = \cfrac{1}{n} |\vec{x}|^2$  
$\overline{y^2} = \cfrac{1}{n} |\vec{y}|^2$  
所以藉由原始公式 :  
$|\vec{x} \cdot \vec{y}| = \overline{xy} \le |\vec{x}| \cdot |\vec{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點)還要大  
![image](https://hackmd.io/_uploads/S14HS6C_T.png)  

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





















































































