{
  "id": "math/0512301",
  "version": "v2",
  "published": "2005-12-14T02:08:54.000Z",
  "updated": "2007-01-04T07:09:06.000Z",
  "title": "Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above",
  "authors": [
    "Iosif Pinelis"
  ],
  "comment": "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)",
  "journal": "IMS Lecture Notes Monograph Series 2006, Vol. 51, 33-52",
  "doi": "10.1214/074921706000000743",
  "categories": [
    "math.PR"
  ],
  "abstract": "Let $(S_0,S_1,...)$ be a supermartingale relative to a nondecreasing sequence of $\\sigma$-algebras $H_{\\le0},H_{\\le1},...$, with $S_0\\le0$ 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=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+\\tfrac{h}{2})$ is given. Another, similar bound is given under somewhat different conditions. It is shown that these bounds improve significantly upon known bounds.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2007-01-04T07:09:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60E15",
      "60G42",
      "60G48",
      "60G50"
    ],
    "keywords": [
      "binomial upper bounds",
      "tail probabilities",
      "differences",
      "martingales",
      "tail comparison inequality"
    ],
    "tags": [
      "monograph",
      "journal article",
      "lecture notes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....12301P"
    }
  }
}