Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above

Abstract

Let $(S_0,S_1,...)$ be a supermartingale relative to a nondecreasing sequence of $\sigma$-algebras $H_{\le 0},H_{\le 1},...$, with $S_0\le 0$ almost surely (a.s.) and differences $X_i:=S_i-S_{i-1}$. Suppose that $X_i\le d$ and $\mathsf{Var}(X_i|H_{\le i-1})\le {\sigma }_i^2$ a.s. for every $i=1,2,...$, where $d>0$ and ${\sigma }_i>0$ are non-random constants. Let $T_n:=Z_1+...+Z_n$, where $Z_1,...,Z_n$ are i.i.d. r.v.'s each taking on only two values, one of which is $d$, and satisfying the conditions $\mathsf{E}{Z}_i=0$ and $\mathsf{Var}{Z}_i={\sigma }^2:=\frac{1}{n}({\sigma }_1^2+...+{\sigma }_n^2)$. Then, based on a comparison inequality between generalized moments of $S_n$ and $T_n$ for a rich class of generalized moment functions, the tail comparison inequality $$ \mathsf P(S_n\ge y) \le c \mathsf P^{\mathsf Lin,\mathsf L C}(T_n\ge y+\tfrach2)\quad\forall y\in \mathbb R$$ is obtained, where $c:=e^2/2=\mathrm{3.694...}$, $h:=d+{\sigma }^2/d$, and the function $y\mapsto {\mathsf{P}}^{\mathsf{Lin},\mathsf{LC}}(T_n\ge y)$ is the least log-concave majorant of the linear interpolation of the tail function $y\mapsto \mathsf{P}(T_n\ge y)$ over the lattice of all points of the form $nd+kh$ ($k\in \mathbb{Z}$). An explicit formula for ${\mathsf{P}}^{\mathsf{Lin},\mathsf{LC}}(T_n\ge y+\frac{h}{2})$ is given. Another, similar bound is given under somewhat different conditions. It is shown that these bounds improve significantly upon known bounds.

Published at http://dx.doi.org/10.1214/074921706000000743 in the IMS Lecture Notes Monograph Series (http://www.imstat.org/publications/lecnotes.htm) by the Institute of Mathematical Statistics (http://www.imstat.org)