1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Maybe it is standard, but what do you exactly denote by $D^2(\cdot) (I mean in terms of conditional expectation)? $\endgroup$ Aug 24, 2015 at 15:52
  • $\begingroup$ Sorry, Soviet notation for variance: $D^2(X | Y) = E( (X-E[X|Y])^2 | Y)$ $\endgroup$ Aug 24, 2015 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$ Aug 24, 2015 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$ Aug 24, 2015 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$ Aug 24, 2015 at 23:05

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Hi Marek, Can you mark the question as answered? $\endgroup$ Dec 3, 2015 at 11:19

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.