1
$\begingroup$

I went through several martingales concentration bounds, but none of them fit the settings I am interested in, which is the following. Suppose I have a sequence of nonnegative random variables $0=Y_{0},\ldots,Y_{n}$, where every $Y_{i}$ is a function of some real random variables $X_{1},\ldots,X_{i}$ and I know that $$ \mathbb{E}[Y_{i+1}-Y_{i} | X_{1},\ldots,X_{i}] \le c_{i}(1-i\sqrt{Y_{i}}) $$ for some small $c_{i}$-s. I believe that in such cases we can say, informally, the sequence is "almost" a supermartingale from some $i$ onwards. Can I bound $\Pr[Y_{n} \ge \alpha]$, as a function of the $c_{i}$-s? It seems plausible that this sequence cannot grow rapidly, with high probability. However, I failed to deduce such a bound.

Thank you very much.

$\endgroup$

1 Answer 1

1
$\begingroup$

We can use the decomposition $$Y_n=\sum_{i=0}^{n-1} Y_{i+1}-Y_i -\mathbb E[Y_{i+1}-Y_i\mid X_1,\dots, X_i ] + \sum_{i=0}^{n-1}\mathbb E[Y_{i+1}-Y_i\mid X_1,\dots, X_i ],$$ hence by assumption, the bound $$Y_n\leqslant \sum_{i=0}^{n-1} Y_{i+1}-Y_i -\mathbb E[Y_{i+1}-Y_i\mid X_1,\dots, X_i ] + \sum_{i=0}^{n-1} c_i(1-i\sqrt{Y_i}) $$ holds. We thus have for a fixed $\alpha$, $$\mathbb P(Y_n\geqslant \alpha)\leqslant \mathbb P\left( \sum_{i=0}^{n-1} Y_{i+1}-Y_i -\mathbb E[Y_{i+1}-Y_i\mid X_1,\dots, X_i ]\geqslant\frac\alpha 2 \right)+\\ +\mathbb P\left(\sum_{i=0}^{n-1} c_i(1-i\sqrt{Y_i})\geqslant\frac\alpha 2 \right) =:P_1+ P_2.$$ An upper bound for $P_1$ can be found using for example Azuma's inequality if the increments are bounded, or Burkholder's inequality in general. And $P_2$ admits an upper bound which may be expressed with the $c_i$-s. For example, if $\alpha\geqslant 2\sum\limits_{i=0}^{n-1}c_i$, then $P_2=0$, hence for such $\alpha$-s, the bound reduces to concentrations inequalities for martingales, which has been extensively studied.

$\endgroup$
2
  • $\begingroup$ Thank you very much, @Davide, but I may be missing something here. Say $c_{i} = (i+1)^{-2}$. How is upper-bounding $P_{2}$ an easier task than the original question (note that in my original post, the term is $i\sqrt{Y_{i}}$)? $\endgroup$
    – Daniel86
    Jan 10, 2015 at 19:11
  • 1
    $\begingroup$ The probability $P_2$ is equal to $0$ if $\alpha /2\geqslant \sum_{i=0}^{n-1} c_i$, so the bound is good for $\alpha$ large. $\endgroup$ Jan 10, 2015 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.