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 all }n\ge N\bigg) \le \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?

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?

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 \epsilon \text{ for some }n\le N) \le \exp\left (-\frac{\epsilon^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 all }n\ge N\bigg) \le \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?

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 all }n\ge N\bigg) \le \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?

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(\|X_1 + \ldots + X_n\| \ge \epsilon \text{ for some }n\le N) \le \exp\left (-\frac{\epsilon^2}{2NL} \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}\|X_1 + \ldots + X_N\| \ge 1\bigg) \le \exp\left (-\frac{N}{2L} \right).$$

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

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

The sum can be bounded by the integral

$$\sum_{n=N}^\infty\exp\left (-\frac{n}{2L} \right) \le \int_{N-1}^\infty\exp\left (-\frac{x}{2L} \right) = 2L \exp\left (-\frac{N-1}{2L} \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}\|X_1 + \ldots + X_n\|_2 <1$ we force $\frac{1}{N}\|X_1 + \ldots + X_N\|_2 <1/2$. This forces the next $\frac{1}{n}\|X_1 + \ldots + X_n\|_2 <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}\|X_1 + \ldots + X_{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}{8} \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}{8} \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?

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 \epsilon \text{ for some }n\le N) \le \exp\left (-\frac{\epsilon^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 all }n\ge N\bigg) \le \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?