# Tail bound for a martingale

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?

• Maybe it is standard, but what do you exactly denote by $D^2(\cdot) (I mean in terms of conditional expectation)? – Davide Giraudo Aug 24 '15 at 15:52 • Sorry, Soviet notation for variance:$D^2(X | Y) = E( (X-E[X|Y])^2 | Y)$– Marek Adamczyk Aug 24 '15 at 19:06 • 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. – Davide Giraudo Aug 24 '15 at 21:08 • 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$. – Marek Adamczyk Aug 24 '15 at 22:56 • 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}$– Marek Adamczyk Aug 24 '15 at 23:05 ## 1 Answer 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\$.

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