Skip to main content
added 213 characters in body
Source Link
Davide Giraudo
  • 4k
  • 2
  • 30
  • 42

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-\sqrt{Y_i}) $$$$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-\sqrt{Y_i})\geqslant\frac\alpha 2 \right) =:P_1+ P_2.$$$$\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 expresedexpressed 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.

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-\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-\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 expresed with the $c_i$-s.

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.

Source Link
Davide Giraudo
  • 4k
  • 2
  • 30
  • 42

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-\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-\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 expresed with the $c_i$-s.