Skip to content
nonconvexcard

Azuma for a random walk with drift

ProofIntermediate⏱ 30 minHigh-Dim Probabilityazumamartingalerandom walk

Problem

Let Y1,Y2,…Y_1,Y_2,\dots be adapted to a filtration with ∣Yk∣≤1|Y_k|\le1 and E[Yk∣Fk−1]=μk\E[Y_k\mid\mathcal F_{k-1}] = \mu_k, where μk\mu_k is Fk−1\mathcal F_{k-1}-measurable. Set Sn=∑k≤nYkS_n = \sum_{k\le n}Y_k and Mn=∑k≤nμkM_n = \sum_{k\le n}\mu_k. Prove that

P(Sn−Mn≥t)≤exp⁡(−t28n).\P\big(S_n - M_n \ge t\big) \le \exp\left(-\frac{t^2}{8n}\right).

Note carefully that the YkY_k are neither independent nor identically distributed.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
Derive Hoeffding's inequality from Hoeffding's lemmaHigh-Dim ProbabilityProofIntermediate30 min
Locating the Bernstein crossoverHigh-Dim ProbabilityNumericalIntermediate30 min
Simulate and compare the concentration inequalities runHigh-Dim ProbabilityCodingIntermediate1 hour
Applying McDiarmid to a medianHigh-Dim ProbabilityProofAdvanced30 min