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

  1. \displaystyle \begin{array}{rcl} \mathbb{E}[S_n^2] & \geq & \mathbb{E}[S_n^2 \mathbb{I}_A] \\ &=& \sum_{k=1}^{n}\left(\mathbb{E}[S_n^2 \mathbb{I}_{A_k}] \right) \\ &=& \sum_{k=1}^{n} \int_{A_k} S^2_n dP \\ &=& \sum_{k=1}^{n} \int_{A_k} \left( S^2_k + 2 S_k (S_n - S_k)+ (S_n - S_k)^2 \right) dP \\ &=& \sum_{k=1}^{n} \int_{A_k} S^2_k dP + 2 \underbrace{ \sum_{k=1}^{n} \int_{A_k} S_k (S_n - S_k)}_{0 \text{ since } S_k, (S_n-S_k) \text{ independent}}dP + \underbrace{ \sum_{k=1}^{n} \int_{A_k} (S_n - S_k)^2 }_{\geq 0} dP \\ &\geq& \sum_{k=1}^{n} \int_{A_k} S^2_k dP \geq \sum_{k=1}^{n} \varepsilon^2 P(A_k) = \varepsilon^2 P(A) = \varepsilon^2 P(\{ \max_{1 \leq k \leq n} |S_K| \geq \varepsilon \}) \end{array}

    \Box

  2. If also {P(|X_i| \leq c) =1, i \leq n}, then

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

    Proof: Notice that

    \displaystyle \mathbb{E}[S_n^2 \mathbb{I}_A] = \mathbb{E}[S_n^2] - \mathbb{E}[S_n^2 \mathbb{I}_{A^c}] \geq \mathbb{E}[S_n^2] - \underbrace{ \varepsilon^2 P(A^c) }_{\text{By Markov Inequality}} = \mathbb{E}[S_n^2] - \varepsilon^2 + \varepsilon^2 P(A) \ \ \ \ \ (1)

    One the set {A_k}

    \displaystyle |S_{k-1}| \leq \varepsilon, \qquad |S_k| \leq |S_{k-1}| + |X_k| \leq \varepsilon + c

    and thus

    \displaystyle \begin{array}{rcl} \mathbb{E}[S_n^2 \mathbb{I}_A] &\underbrace{=}_{\text{by preceding proof}}& \sum_{k=1}^{n} \int_{A_k} \left( S_k+ (S_n - S_k) \right)^2 dP \\ &=& \sum_{k=1}^{n} \mathbb{E}[S_k^2\mathbb{I}_{A_k}] + \sum_{k=1}^{n} \mathbb{E}[(S_n-S_k)^2\mathbb{I}_{A_k}] \\ &\leq& (\varepsilon+c)^2 \sum_{k=1}^{n} P(A_k) + \sum_{k=1}^{n} P(A_k) \sum_{i=k+1}^{n}\mathbb{E}[X_i^2] \\ &\leq& P(A) \left[ (\varepsilon+c)^2 + \sum_{i=1}^{n}\mathbb{E}[X_i^2] \right] \\ &=& P(A)\left[ (\varepsilon+c)^2 + \mathbb{E}[S_n^2] \right] \end{array}

    Combining the above result and 1 we have

    \displaystyle P(A)\left[ (\varepsilon+c)^2 + \mathbb{E}[S_n^2] \right] \geq \mathbb{E}[S_n^2 \mathbb{I}_A] \geq \mathbb{E}[S_n^2] - \varepsilon^2 + \varepsilon^2 P(A)

    and hence

    \displaystyle P(A) \geq \frac{\mathbb{E}[S_n^2]- \varepsilon^2}{(\varepsilon+c)^2 + \mathbb{E}[S_n^2] - \varepsilon^2} = 1 - \frac{(\varepsilon+c)^2}{\varepsilon+c)^2+\mathbb{E}[S_n^2]-\varepsilon^2} \geq 1 - \frac{(c+\varepsilon)^2}{\mathbb{E}[S_n^2]}

    \Box

Advertisements
This entry was posted in Inequalities, Statistics and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s