The setup is as follows. We are given a martingale $X_0,X_1,...,X_k$. The difference $X_i-X_{i-1}$ is always between $[-1,1]$. Variance $D^2(X_i-X_{i-1}| X_{i-1})$ is something, but we can show that after taking expectation on $X_{i-1}$ then we get that $D^2(X_i-X_{i-1}) \leq X_0/k$. Therefore, I would like to get a tail bound $P( X_k - X_0 > t) \leq \exp(-t^2/ X_0 )$; constants in the exponent don't matter. There exists a similar bound $P( X_k - X_0 > t) \leq \exp(-\frac{t^2}{\sum_{i=1}^k c_i^2} )$, but here $c_i^2$ is the bound on supremum of $D^2(X_i-X_{i-1}| X_{i-1})$ for the worst-case $X_{i-1}$, so this one does not imply what I want.

How can I get a hold on a bound like that?

  • $\begingroup$ Maybe it is standard, but what do you exactly denote by $D^2(\cdot) (I mean in terms of conditional expectation)? $\endgroup$ – Davide Giraudo Aug 24 '15 at 15:52
  • $\begingroup$ Sorry, Soviet notation for variance: $D^2(X | Y) = E( (X-E[X|Y])^2 | Y)$ $\endgroup$ – Marek Adamczyk Aug 24 '15 at 19:06
  • $\begingroup$ Thanks. How do you deduce that this is smaller than $X_0/k$? This implies that $X_0\geqslant 0$ which is not the case in general. But as I understand it is true in your situation. $\endgroup$ – Davide Giraudo Aug 24 '15 at 21:08
  • $\begingroup$ the martingale is actually composed of two random sequences, i.e. $X_t = Y_t + Z_t$. We start with $Y_0 = 0$, and $Z_0$ being some arbitrary value. At step $t+1$ we subtract from $Z_t$ quantity equal on expectation to $\frac{1}{k-t}Z_t$, and to $Y_t$ we add quantity on expectation equal to $\frac{1}{k-t}Z_t$. Since the change is always less than $1$, then we can argue that the variance is at most $\frac{1}{k-t}Z_t$ (maybe times two, forget the constants). Inductively one can show that $E Z_t = (1-t/k)Z_0$. $\endgroup$ – Marek Adamczyk Aug 24 '15 at 22:56
  • $\begingroup$ Also, as for the bound, little change. I need to upperbound $e^{\lambda \cdot Y_k}$ by $e^{(e^\lambda - 1) EY_k}$, or something similar that would yield the same asymptotic bound for the uppertail: $P(Y_k > (1+\delta) E Y_k) < (\frac{e^\delta}{(1+\delta)^{(1+\delta)}})^{E Y_k}$ $\endgroup$ – Marek Adamczyk Aug 24 '15 at 23:05

Alas, the general bound you are hoping for cannot hold. Take $X_0:=1$ and continue the sequence as a simple random walk with probability $1/k$ and as the all ones sequence with probability $1-1/k$. Then for $t=\sqrt{k}$, the chance that $X_k-X_0>t$ is at least $C/k$ for some constant $C>0$.

  • $\begingroup$ Hi Marek, Can you mark the question as answered? $\endgroup$ – Yuval Peres Dec 3 '15 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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