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

An inequality of the mean involving truncation

Let ${X_1,X_2,...}$ be i.i.d. r.vs with ${\mathbb{E}[|X_i|] < \infty}$ and ${Y_k = X_k \mathbb{I}_{(|X_k| \leq k)}}$. Then

$\displaystyle \boxed{ \mathbb{E}[X_1] \geq \sum_{k=1}^{\infty} \frac{var(Y_k)}{4 k^2 } }$

Proof:

First we proove the following useful result

If ${X \geq 0}$ and ${ a > 0}$ then

$\displaystyle \boxed{ \mathbb{E}[X^a] = \int_{0}^{\infty} a x^{a-1} P(X >x) dx }$

$\displaystyle \begin{array}{rcl} \int_{0}^{\infty} a x^{a-1} P(X >x) dx &=& \int_{0}^{\infty} \int_{\Omega}a x^{a-1} \mathbb{I}_{(X>x)} dP dx \\ &=& \int_{\Omega} \int_{0}^{\infty} a x^{a-1} \mathbb{I}_{(X>x)} dP dx \\ &=& \int_{\Omega} \int_{0}^{X} a x^{a-1} dP dx = \mathbb{E}[X^a] \end{array}$

Note you can find the same lemma on Feller Vol.2 (p. 150) as

$\displaystyle \mathbb{E}[X^a]= \int_{0}^{\infty} x^a F \{ dx \} = a \int_{0}^{\infty} x^{a-1} [ 1- F(x)] dx$

Some notes on Kalman Filtering

State Space form

Measurement Equation

$\displaystyle \boxed{\mathbf{\underbrace{y_{t}}_{N \times 1}=\underbrace{Z_{t}}_{N \times m}\underbrace{a_{t}}_{m \times 1}+d_{t}+\varepsilon_{t}}}$

$\displaystyle Var(\varepsilon_{t})= \mathbf{H_{t}}$

Transition Equation

$\displaystyle \boxed{\mathbf{\underbrace{a_{t}}_{m \times 1} =\underbrace{T_{t}}_{m \times m} a_{t-1}+c_{t}+\underbrace{R_{t}}_{m \times g} \underbrace{\eta_{t}}_{g \times 1}}}$

$\displaystyle Var(\eta_{t})=\mathbf{Q}_{t}$

$\displaystyle E(a_{0})= \mathbf{a_{0} \; \; \; \; Var(a_{0})=P_{0}} \; \; \; \; E(\varepsilon_{t}a_{0}^{\top}) \; \; \; E(\eta_{t}a_{0}^{\top})$

Future form

$\displaystyle \mathbf{a_{t+1}=T_{t}a_{t}+c_{t}+R_{t}\eta_{t}}$

Big Data for Volatility vs.Trend

So different aspects of Big Data — in this case dense vs. tall — are of different value for different things.  Dense data promote accurate volatility estimation, and tall data promote accurate trend estimation.

More (No Hesitations blog)