Suppose $f_0,f_1, \ldots$ is a martingale (or i.i.d sequence) in $\mathbb R^d$ with $f_0=0$ and all $\|f_n - f_{n-1}\| \le L$ say. There are many concentration results for the initial segment of the martingale. For example Theorem 3.5 of this paper of Pinelis leads to the following variant of the Azuma-Hoeffding inequality.

$$P(\|f_n\| \ge \varepsilon \text{ for some }n\le N) \le \exp\left (-\frac{\varepsilon^2}{2NL^2} \right).\tag 1$$

In the paper such results are called tail inequalities for martingales. What I'm interested in could also be called a tail inequality, except I am interested in is the behaviour after $N$ rather than before. Of course there's no reason to believe since $f_1,f_2,\ldots$ should remain bounded, but if we instead focus on the normalised values $\frac{f_n}{n}$ we can get some bounds. For example taking $\epsilon = N$ the Pinelis theorem implies

$$P\bigg (\frac{1}{N}\|f_N\| \ge 1\bigg) \le \exp\left (-\frac{N}{2L^2} \right).$$

The crudest thing we can do is take a union bound to get

$$P\bigg (\frac{1}{n}\|f_n\| \ge 1\text{ for some }n\ge N\bigg) \le \sum_{n=N}^\infty\exp\left (-\frac{n}{2L^2} \right).$$

and hence

$$P\bigg (\frac{1}{n}\|f_n\| \le 1\text{ for all }n\ge N\bigg) \ge 1-\sum_{n=N}^\infty\exp\left (-\frac{n}{2L^2} \right).$$

The sum can be bounded by the integral

$$\sum_{n=N}^\infty\exp\left (-\frac{n}{2L^2} \right) \le \int_{N-1}^\infty\exp\left (-\frac{x}{2L^2} \right) = 2L \exp\left (-\frac{N-1}{2L^2} \right)$$

which goes to zero as $N \to \infty$.

I am wondering if there are any more sophisticated approaches to get better bounds?

One idea I had was, instead of forcing each $\frac{1}{n}\|f_n\| <1$ we force $\frac{1}{N}\|f_N\|_2 <1/2$. This forces the next $\frac{1}{n}\|f_n\| <1$ for all $n \le \left(\frac{2L}{2L-1/2}\right)N$. Then for $n_1 = \left(\frac{2L}{2L-1/2}\right)N$ we force $\frac{1}{n_1}\|f_{n_1}\|_2 <1/2$ and so on. Proceeding like this we get a union bound over $N,n_1,n_2,\ldots$ leading to a series of the form

$$\sum_{n=1}^\infty \exp \left( \frac{N}{8L^2} \left(\frac{2L}{2L-1/2}\right)^{n-1}\right).$$

and the integral

$$\int_{0}^\infty \exp \left( a b^{x-1}\right) = \int_{-1}^\infty \exp \left( a b^{x}\right)$$

for the obvious constants. Under the substitution $u =ab^{x}$ this becomes the exponential integral function

$$\frac{1}{\log b}\int_{a/b}^\infty \frac{e^{-t}}{t}dt = \frac{\text{Ei}_1(a/b)}{\log b}.$$

Using some special function inequalities I can bound the above by

$$\frac{e^{-a/b}}{(a/b)\log b}$$

which simplifies to something of the form

$$\frac{C \exp \left( \frac{N}{8L^2} \frac{2L-1/2}{2L}\right) }{N}$$.

We have acquired a $N$ in the denominator, and maybe a smaller coefficient $C$ than before. Unfortunately this makes no difference asymptotically because the coefficient inside the exponential is smaller than before.

You can also replace $1/2$ with any $\delta \in (0,1)$, perform the calculations, and try to minimise the result with respect to $\delta$. There is a closed form solution for such a $\delta$ but it is the solution of a cubic equation so doesn't offer much insight.

One could also try different $\delta_i$-values between each $n_i$ and $n_{i+1}$ but I cannot see how to bound the resulting series with an integral.

Has this problem been considered before? Could anyone provide a reference?

  • $\begingroup$ Iosif Pinelis is a user here, @IosifPinelis , he may have some insightful comments. (My intuition is that one cannot do much better than in your first approach, but that is just intuition). $\endgroup$ – Mateusz Kwaśnicki May 30 '19 at 8:06
  • $\begingroup$ @MateuszKwaśnicki : I too think one cannot do much better than that, but proving rigorously "cannot do" statements is usually too hard and not very gratifying. $\endgroup$ – Iosif Pinelis May 31 '19 at 18:41
  • $\begingroup$ Daron, Can you make your question more precise? The title line has parenthesis in the wrong place and later on when you write "The crudest thing we can do is take a union bound to get $$P\bigg (\frac{1}{n}\|f_n\| \ge 1\text{ for all }n\ge N\bigg) \le \sum_{n=N}^\infty\exp\left (-\frac{n}{2L^2} \right) ",$$ you are using a union bound for an intersection... Thanks. $\endgroup$ – Yuval Peres Jun 1 '19 at 1:54
  • $\begingroup$ Hey Yuval, sure thing! $\endgroup$ – Daron Jun 1 '19 at 13:27
  • $\begingroup$ Thanks for the feedback everyone. I'm surprised no one has seen something like this before. I'd imagine if the answer was no, then you'd be able to demonstrate that using the normal coin-flip martingale, but that would involve some very clever recursion tricks. $\endgroup$ – Daron Jun 11 '19 at 15:44

Your Answer

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

Browse other questions tagged or ask your own question.