-
Multiplicative Chernoff v.s. Additive Chernoff: Which One Is Stronger?
Jun 09, 2018
Let me first show their definitions from Wikipedia 1. Note that the domain of random variables can be extended from $\{ 0, 1 \}$ to $[0, 1]$ just noting that $\E \left[ e^{tX_i} \right] \leq \E[X_i] \cdot e^t + (1 - \E[X_i])$. Additive Chernoff bound Suppose $X_1, \dots, X_n$ are i.i.d. random variables supported on $[0, 1]$. Let $\E[X_i] = \mu$ and $\bar{X} = \frac{1}{n} \sum_{i = 1}^n X_i$. Then, we have…
-
An Application of Doob's Martingale Inequality
Mar 23, 2018
Problem Suppose we have a sequence of i.i.d. Gaussian random variables $X_t$'s with bounded variance. Let $S_n = \sum_{t = 1}^n X_t$. How can we bound the probability of \begin{equation} \label{eq:problem} \left \{ \max_{1 \leq t \leq n} S_t > \eps \right \}? \end{equation} Sub-gaussian random variables To make this problem more realistic, it is always safe to loose Gaussian random variables to zero mean sub-gaussian random variables. Intuitively, sub-gaussian r.…
-
Test
Dec 02, 2017
This is a post for testing latex formulas. Inline formulas $e^{ix} = \cos x + i \sin x$. Display formulas $$ \sum_{i = 1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}. $$