Hoeffding’s Inequality

Let {X_1,...,X_n} be independent zero-mean real valued variables and let {S_n= \sum\limits_{i=1}^{n} X_i.} Then

\displaystyle \begin{array}{rcl} \text{If } a_i \leq X_i \leq b_i; \qquad &i&=1,..,n \text{ where } a_1, b_1,...,a_n, b_n \text{ constant then } \\ P(|S_n| \geq t) &\leq& 2 \exp \left( - \frac{2t^2}{\sum\limits_{i=1}^{n} (b_i-a_i)^2} \right), \qquad t>0 \end{array}

Continue reading “Hoeffding’s Inequality”

Advertisements

Expectation: Useful properties and inequalities

Screenshot - 110614 - 16:15:09

If {X \geq 0} is a random variable on {(\Omega, \mathcal{F}, P)}. The expected value of {X } is defined as

\displaystyle \mathbb{E}(X) \equiv \int_{\Omega} X dP = \int_{\Omega} X(\omega) P (d \omega)

Inequalities

  • Jensen’s inequality. If {\varphi} is convex and {E|X|, E|\varphi(X)| < \infty}

\displaystyle \mathbb{E} (\varphi(X)) \geq \varphi(\mathbb{E}X)

  • Holder’s inequality. If {p,q \in [1, \infty]} with {1/p + 1/q =1} then

\displaystyle \mathbb{E}|XY| \leq \|X\|_p \|Y\|_q

  • Cauchy-Schwarz Inequality: For {p=q=2}

\displaystyle \mathbb{E}|XY| \leq \left( \mathbb{E}(X^2) \mathbb{E}(Y^2) \right)^{1/2}

Continue reading “Expectation: Useful properties and inequalities”