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

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”