An Application of Doob's Martingale Inequality

Mar 23, 2018

Problem

Suppose we have a sequence of i.i.d. Gaussian random variables Xt's with bounded variance. Let Sn=t=1nXt. How can we bound the probability of

(1){max1tnSt>ϵ}?

Sub-gaussian random variables

To make this problem more realistic, it is always safe to loose Gaussian random variables to zero mean sub-gaussian random variables.

Intuitively, sub-gaussian r.v.‘s have tails decreasing as fast as those of Gaussian r.v.‘s. Hence, most of the inequalities related to Gaussian r.v.‘s can be safely applied to sub-gaussians without any modifications! You are suggested to refer to Subgaussian random variables: An expository note for more details. Here, we assume Xt is a σ-subgaussian r.v. which is comparable to a Gaussian r.v. with variance σ2.

An elementary property of σ-subgaussian random variable X is

(2)E[exp(λX)]exp(λ2σ2/2).

Also, it is useful to know the following facts:

  • St is tσ-subgaussian,
  • and P(X>ϵ)exp(ϵ22σ2).

A naive way

Obviously, we can use a union bound to give a naive bound.

For each t, since St is tσ-subgaussian we have P(St>ϵ)exp(ϵ22tσ2). Via a union bound, we get

P(max1tnSt>ϵ)t=1nexp(ϵ22tσ2),

from which we can see the upper bound is no less then

(3)nexp(ϵ22nσ2).

This bound is very loose. Later, you will see the reason.

An alternative way

Doob’s martingale inequality

The formal statement of Doob’s martingale inequality can be found in 1. We restate it in the following.

Suppose the sequence T1,,Tn is a submartingale, taking non-negative values. Then it holds that

(4)P(max1tnTt>ϵ)E[Tn]ϵ.

With this tool in mind, we are now ready to bound (1) in another way.

Using standard Chernoff’s method, for any λ>0, we have

P(max1tnSt>ϵ)=P(max1tnexp(λSt)>exp(λϵ)).

Since E[exp(λXt)]exp(E[λXt)]=1, sequence exp(λS1),,exp(λSt) is a submartingale. (This is a good exercise. You can validate it by yourself.) By (4), we further have

P(max1tnSt>ϵ)E[exp(λSn)]exp(λϵ)=t=1nE[exp(λXt)]exp(λϵ)exp(λ2σ2n2λϵ),

where the second equality is due to the mutual indenpendency of Xt's, and the last inequality is due to (2).

The minimum is achieved when λ=ϵσ2n. So we finally get

P(max1tnSt>ϵ)exp(ϵ22nσ2),

which is only one n-th of (3)!

Note that Lemma 2 in 2 gives the same statement. However, I think it is more direct to use Doob’s martingale inequality.


  1. Doob’s martingale inequality , Wikipedia. ↩︎

  2. Shengjia Zhao, Enze Zhou, Ashish Sabharwal, and Stefano Ermon. Adaptive Concentration Inequalities for Sequential Decision Problems . In NIPS, pages 1343–1351, 2016. ↩︎

mathprobability

Generate New Posts by Shell Scripts

Test