# 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}$

# Almost sure convergence via pairwise independence

If ${A_1,A_2,...}$ are pairwise independent and ${\sum_{n=1}^{\infty}P(A_n)=\infty}$ then as ${n \rightarrow \infty}$

$\displaystyle \boxed{ \frac{\sum_{m=1}^{n}\mathbb{I}_{A_m}}{\sum_{m=1}^{n}P(A_m)} \xrightarrow{a.s.} 1 }$

Proof:

Let ${X_m = \mathbb{I}_{A_m}}$ and ${S_n = X_1+...+Xn}$. Since ${A_m}$ are pairwise independent, the ${X_m}$ are uncorrelated and thus

$\displaystyle var(S_n) = var(X_1) + ... + var(X_n)$

Since ${X_m \in \{0,1 \}}$

$\displaystyle var(X_m) \leq \mathbb{E}[X_m^2] = \mathbb{E}[X_m] \Rightarrow var(S_n) \leq \mathbb{E} [S_n]$

# Expectation: Useful properties and inequalities

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}$

# Very brief notes on measures: From σ-fields to Carathéodory’s Theorem

Definition 1. A ${\sigma}$-field ${\mathcal{F}}$ is a non-empty collection of subsets of the sample space ${\Omega}$ closed under the formation of complements and countable unions (or equivalently of countable intesections – note ${\bigcap_{i} A_i = (\bigcup_i A_i^c)^c}$). Hence ${\mathcal{F}}$ is a ${\sigma}$-field if

$1. {A^c \in \mathcal{F}}$ whenever ${A \in \mathcal{F}}$
$2. {\bigcup_{i=1}^{\infty} A_i \in \mathcal{F}}$ whenever ${A_i \in \mathcal{F}, n \geq 1}$

Definition 2. Set functions and measures. Let ${S}$ be a set and ${\Sigma_0}$ be an algebra on ${S}$, and let ${\mu_0}$ be a non-negative set function

$\displaystyle \mu_0: \Sigma_0 \rightarrow [0, \infty]$

• ${\mu_0}$ is additive if ${\mu_0 (\varnothing) =0}$ and, for ${F,G \in \Sigma_0}$,

$\displaystyle F \cap G = \varnothing \qquad \Rightarrow \qquad \mu_0(F \cup G ) = \mu_0(F) + \mu_0(G)$

• The map ${\mu_0}$ is called countably additive (or ${\sigma}$-additive) if ${\mu (\varnothing)=0}$ and whenever ${(F_n: n \in \mathbb{N})}$ is a sequence of disjoint sets in ${\Sigma_0}$ with union ${F = \cup F_n}$ in ${\Sigma_0}$, then

$\displaystyle \mu_0 (F) = \sum_{n}\mu_0 (F_n)$

• Let ${(S, \Sigma)}$ be a measurable space, so that ${\Sigma}$ is a ${\sigma}$-algebra on ${S}$.
• A map $\displaystyle \mu: \Sigma \rightarrow [0,\infty].$ is called a measure on ${(S, \Sigma)}$ if ${\mu}$ is countable additive. The triple ${(S, \Sigma, \mu)}$ is called a measure space.
• The measure ${\mu}$ is called finite if

$\displaystyle \mu(S) < \infty,$

and ${\sigma}$finite if

${\exists \{S_n\} \in \Sigma}$, (${n \in \mathbb{N}}$) s.th.$\displaystyle \mu(S_n)< \infty, \forall n \in \mathbb{N} \text{ and } \cup S_n = S.$

• Measure ${\mu}$ is called a probability measure if $\displaystyle \mu(S) = 1,$ and ${(S, \Sigma, \mu)}$ is then called a probability triple.
• An element ${F}$ of ${\Sigma}$ is called ${\mu}$-null if ${\mu(F)=0}$.
• A statement ${\mathcal{S}}$ about points ${s}$ of ${\mathcal{S}}$ is said to hold almost everywhere (a.s.) if

$\displaystyle F \equiv \{ s: \mathcal{S}(s) \text{ is false} \} \in \Sigma \text{ and } \mu(F)=0.$

Continue reading “Very brief notes on measures: From σ-fields to Carathéodory’s Theorem”

# Rio’s Inequality

Let ${X}$ and ${Y}$ be two integrable real-valued random variables and let ${ Q_x(u) = inf\{t: P(|X|>t) \leq u \}}$ be the quantile function of ${|X|}$. Then if ${Q_X Q_Y}$ is integrable over ${ (0,1)}$ we have

$\displaystyle \boxed{|Cov(X,Y)| \leq 2 \int\limits_{0}^{2a} Q_x(u) Q_Y(u) du}$

where ${ a= a(\sigma(X), \sigma(Y)) = \sup\limits_{\substack{B \in \mathcal{B} \\ C \in \mathcal{C}}} |Cov(\mathbb{I}_{\sigma(X)},\mathbb{I}_{\sigma(Y)})|}$ is the a-mixing coefficient.

Proof: Set ${X^{+} = sup(0,X)}$ and ${X^{-} = sup(0,-X)}$ then

$\displaystyle Cov(X,Y) = Cov(X^{+},Y^{+}) + Cov(X^{-},Y^{-}) - Cov(X^{+},Y^{-}) - Cov(X^{-},Y^{+})$

since ${ X = (X^{+} - X^{-})}$ and ${ Y = (Y^{+} - Y^{-})}$

note also that

$\displaystyle Cov(X^+,Y^+) = \int \int_{\mathbb{R}^{2}_{+}} [P(X>u, Y> \upsilon) - P(X>u)P(Y> \upsilon)]du d\upsilon$

which implies that

$\displaystyle |Cov(X^+,Y^+)| \leq \int \int_{\mathbb{R}^{2}_{+}} \inf (a, P(X>u),P(Y> \upsilon))du d\upsilon$

# Kolmogorov’s Maximal Inequality

1. Let ${X_1, X_2,...,X_n}$ be independent random variables with ${ \mathbb{E}[X_i]=0, \mathbb{E}[X_i^2]< \infty }$. Set ${S_n = \sum_{i=1}^{n} X_n}$. Then ${\forall \varepsilon > 0}$

$\displaystyle \boxed{ P \left( \max_{1 \leq k \leq n} |S_K| \geq \varepsilon \right) \leq \frac{\mathbb{E}[S_n^2]}{\varepsilon^2} }$

Proof: Let

$\displaystyle \begin{array}{rcl} A &\equiv& \{ \max_{1 \leq k \leq n} |S_k| \geq \varepsilon \} ,\\ A_k &\equiv& \{ |S_i| < \varepsilon, i=1,...,k-1,|S_k| \geq \varepsilon \}, \qquad 1 \leq k \leq n \end{array}$

Notice that ${\cup_{i=1}^{n}A_k = A}$ and