Skip to main content
MathOverflow

Return to Question

Typo in title
Source Link
edit approved Jan 10, 2015 at 16:08
Community Bot
edit approved Jan 10, 2015 at 16:08
Community Bot
  • 1
  • 2
  • 3

Concentration bound for a martingale-like setting (the exptectedexpected difference decreases as the sequence increases)

I went through several martingales concentration bounds, but none of them fit to 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 casecases 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.

Concentration bound for a martingale-like setting (the exptected difference decreases as the sequence increases)

I went through several martingales concentration bounds, but none of them fit to 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 case 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.

Concentration bound for a martingale-like setting (the expected difference decreases as the sequence increases)

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.

Source Link
Daniel86
Daniel86
  • 225
  • 1
  • 8

Concentration bound for a martingale-like setting (the exptected difference decreases as the sequence increases)

I went through several martingales concentration bounds, but none of them fit to 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 case 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.