# 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點)還要大

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