Sagar

Concentration Bounds

Concentration Bounds dominate a lot of the literature in approximate counting. Since it is one of the topics I would like to dive into, here I try to take note of some of them.

I will be following these notes. But before I go there I need to understand Moment generating functions.

Moment Generating Function

Source: Lecture 17: Moment Generating Functions by Joseph K. Blitzstein

Definition: A random variable $X$ has a Moment Generating Function $$M(t) = E[\exp(tX)]$$ as a function of $t$, if $M(t)$ is finite for some interval of $t$ i.e. $M_t$ is finite for all $t \in (-a,a)$, for some $a > 0$.

$M(t)$ is called moment generating because $$E[\exp(tX)] = E\big [\sum_{n=0}^{\infty}\frac{X^{n}t^{n}}{n!}\big] \underset{??}= \sum_{n=0}^{\infty}\frac{E[X^{n}]t^{n}}{n!}$$ The second equality is not trivially true. We need more than linearity of expectation due to the infinite sum. [I dont know how to prove this, Prove it].

Properties of MGF:

  • We can obtain the $n^{th}$ moment i.e. $E[X^{n}]$ by just taking the $n^{th}$ derivative evaluated at $0$ i.e. $M^{(n)}(0) = \frac{d^{n}M(t)}{dt}\big|_{x=0}$.
  • MGF determines the distribution i.e. if $X$ and $Y$ have the same MGF they have the same PDF. [Non-trivial to proove]
  • If $X$ and $Y$, are independent and have the $MGF$ $M_x$ and $M_y$ respectively then $M_{x+y} = M_xM_y$, this is due to the fact that if two RV are independent then expectation of their products is just product of their expectation.

    Markov Inequality

    Although trivial to prove Markov Inequality forms the basis of many other inequalities. Once, you have markov inequality, then you can just use it on functions of the random variable itself (e.g. the moments of a random variable are it's functions too) to get newer bounds.

    Lemma 1. \begin{equation} Pr(X \geq a) \leq \frac{E[X]}{a} \end{equation} Proof. \begin{align*} E[X] &= \sum x P(X = x)\\ E[X] &= \sum_{x \geq a} x P(X=x) + \sum_{x < a} x. P(X = x)\\ E[X] &\geq \sum_{x \geq a} a P(X=x)\\ E[X] &\geq a P(X\geq a)\\ \frac{E[X]}{a} &\geq P(X\geq a) \end{align*}

    Let us try to find the case where markov inequality is met with equality i.e. : \begin{align*} P(X \geq a) = \frac{E[X]}{a} \end{align*}

    Chebyshev's Inequality

    Lemma 2. Given a random variable $X$, such that $X$ has a finite expected value. The standard deviation of $X$ i.e. $\sigma = \sqrt{E[(X - E[X]^{2})]}$ is finite. Then for every constant $a > 0 $: \begin{equation} Pr(|X-E[X]| \geq a) \leq \frac{\sigma^{2}}{a^2} \end{equation} Proof. \begin{equation*} Pr(|X-E[X]| \geq c) = Pr((X-E[X])^{2} \geq c^{2}) \end{equation*} Now, $|X-E[X]|^2$ is a finite random variable it self. Hence, using Markov Inequality, we have that: \begin{align*} Pr(|X-E[X]|^{2} \geq c^{2}) &\geq \frac{E[(X-E[X])^{2}]}{c^{2}}\\ Pr(|X-E[X]|^{2} \geq c^{2}) &\geq \frac{\sigma^{2}}{c^{2}}\\ Pr(|X-E[X]| \geq c) &\geq \frac{\sigma^{2}}{c^{2}}\\ \end{align*} Corollary 2.1. Given a random variable $X$, such that $X$ has a finite expected value. The standard deviation of $X$ i.e. $\sigma = \sqrt{E[(X - E[X]^{2})]}$ is finite. Then for every constant $a > 0 $: \begin{equation} Pr(|X-E[X]| \geq a) \leq \frac{E[|X-E[X]|^{n}]}{a^{n}} \end{equation}

    Tightness of Markov and Chebyshev Inequality: We cant do better than them in general.

    Chernoff Bound