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. BlitzsteinDefinition: 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:
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.