Markov inequality

$\quad$ If $X \ge 0$ and $a > 0$, then

$$\begin{aligned} \mathbb{P}(X \ge a) &\le \frac{\mathbb{E}[X]}{a} \\ \end{aligned}$$

Chebyshev inequality

$$\begin{aligned} \mathbb{P}(|X-\mu| \ge c) &\le \frac{\sigma^2}{c^2} & c > 0 \\ \end{aligned}$$

Weak law of large numbers (WLLN)

$\quad X_1, X_2, \cdots$ i.i.d; finite mean $\mu$ and variance $\sigma^2$

$$\begin{aligned} M_n &= \frac{X_1 + \cdots + X_n}{n} & \text{sample mean} \\ \mathbb{E}[M_n] &= \mu \\ var(M_n) &= \frac{\sigma^2}{n} \\ \mathbb{P}(|M_n - \mu| \ge \epsilon) &\le \frac{\sigma^2}{n\epsilon^2} \rightarrow 0 \quad \text{as } n \rightarrow \infty &\text{ for } \epsilon > 0 \\ \end{aligned}$$

Convergence in probability

$\quad$ A sequence $Y_n$, not necessarily independent, converges in probability to a number $a$ if:

$$\begin{aligned} \lim_{n->\infty}\mathbb{P}(|Y_n - a| \ge \epsilon) = 0 \\ \end{aligned}$$

$\quad$ Caveat: Suppose $X_n \rightarrow a$ in probability, $\mathbb{E}[X_n]$ need not converge to $a$ !
$\quad$ How to check for convergence ? Guess $a$, express the CDF as above, and then check if the limit approaches zero.

Central Limit Theorem

$\quad X_1,\cdots,X_n$ i.i.d with finite mean $\mu$ and variance $\sigma^2$.

$$\begin{aligned} S_n &= X_1 + \cdots + X_n & \text{variance: } n\sigma^2 \\ \frac{S_n}{\sqrt{n}} &= \frac{X_1 + \cdots + X_n}{\sqrt{n}} & \text{variance: } \sigma^2 \\ \color{red}{Z_n} &\color{red}{=} \color{red}{\frac{S_n - n\mu}{\sqrt{n}\sigma}} & S_n \thicksim N(n\mu, n\sigma^2) \\ M_n &= \frac{S_n}{n} & \mathbb{E}[M_n] = \mu \quad var(M_n) = \frac{\sigma^2}{n} \\ \color{red}{Z_n} &\color{red}{=} \color{red}{\frac{M_n - \mu}{\sigma/\sqrt{n}}} & M_n \thicksim N(\mu, \frac{\sigma^2}{n}) \\ \color{red}{\lim_{n \rightarrow \infty} \mathbb{P}(Z_n \le z)} &\color{red}{=} \color{red}{\mathbb{P}(Z \le z)} = \Phi(z) & \text{for every }z, \text{ where } Z \thicksim N(0,1) \\ \end{aligned}$$

Moivre-Laplace 1/2 correction

$\quad$When $a$ is discrete.

$$\begin{aligned} \mathbb{P}(S_n \le a) &\ge p & \text{under estimate} \\ \mathbb{P}(S_n \lt a+1) &\ge p & \text{over estimate} \\ \mathbb{P}(S_n \lt a+0.5) &\ge p & \text{1/2 correction} \\ \end{aligned}$$

Jensen's inequality

$\quad$If $g$ is a convex function (ie a smiley face). Note $g''(x) \ge 0$

$$\begin{aligned} \color{blue}{g(x)} &\color{blue}{\ge g(c) + g'(c) (x-c)} & \text{1st order Taylor expansion} \\ g(X) &\ge g(\mathbb{E}[X]) + g'(\mathbb{E}[X]) (x-\mathbb{E}[X]) & \text{let } c = \mathbb{E}[X] \\ \mathbb{E}[g(X)] &\ge \mathbb{E}[g(\mathbb{E}[X])] + \mathbb{E}\left[g'\big(\mathbb{E}[X]\big) \big(X-\mathbb{E}[X]\big)\right] & \text{note }\mathbb{E}[X] \text{ is a constant} \\ \mathbb{E}[g(X)] &\ge g(\mathbb{E}[X]) + g'(\mathbb{E}[X]) (\mathbb{E}[X]-\mathbb{E}[X]) \\ \color{blue}{\mathbb{E}[g(X)]} &\color{blue}{\ge g(\mathbb{E}[X])} \\ \end{aligned}$$

Hoeffding's inequality

$\quad X_i$ are random variables with i.i.d, and each is equally likely to be either -1 or 1. Let $a \gt 0$

$$\begin{aligned} \mathbb{P}(X_1 + \cdots + X_n \ge na) &\le e^{-na^2/2} & \text{a much stronger bound than Chebyshev inequality} \\ \end{aligned}$$

Source: MITx 6.041x, Lecture 18.

# posted by rot13(Unafba Pune) @ 11:05 PM