Concentration inequalities for the maximum of the rescaled/normalized sum of iid random variables

Question

I am interested in concentration inequalities for the maximum of the rescaled/normalized sum of iid random variables.

Let $X_1,..., X_n$ be i.i.d random variables, $S_n$ their centered sum and $M_n$ the maximum of the partial sums: $$ S_n = \sum_{k=1}^{n}{(X_k - \mu)} \ , \quad M_n = \max_{1 \leq k \leq n}{S_k}$$ In this case, we can easily derive concentration inequalities on $M_n$ using the fact that $S_n$ is a martingale and applying Azuma-Hoeffding's inequality (I don't know whether there are better techniques, if they are, please tell me).

Now, my question is how to derive concentration inequalities for the maximum of the rescaled or normalized sums: $$\max_{1 \leq k \leq n}{\frac{S_k}{k}} = \max_{1 \leq k \leq n}{\hat{\mu}_k-\mu}, \quad \max_{1 \leq k \leq n}{\frac{S_k}{\sqrt{k}}} \quad \text{or more generally} \quad \max_{1 \leq k \leq n}{\frac{S_k}{f(k)}}$$ The problem is we don't have martingales anymore. Of course, it is always possible to derive bounds by summing concentration bounds for each different value of $k$: $$\mathbb{P}(\max_{1 \leq k \leq n}{\hat{\mu}_k-\mu} \geq \varepsilon) \leq \sum_{k=1}^{n}{\mathbb{P}(\hat{\mu}_k-\mu \geq \varepsilon)}$$ but I'm looking for smarter things. In my community (statistics/machine learning, so no pure probabilists), the best technique used is "peeling": decomposing not for all values of $k$ but in slices of exponential length. But since the question is quite natural (at least it looks quite natural to me), I'm sure it must already have been studied. So I'm looking for any results or techniques that could be used to answer my question.

PS : You're free to assume whatever you need on $X_k$, like existence of moments, of the moment generating function, boundedness...

PS2 : I'm looking for finite-time results, not purely asymptotic ones like the Hartman-Wintner theorem/law of the iterated logarithm.

Answer 1

One can use Birnbaum and Marshall inequality:

Theorem(Theorem 2.1. in 1). If $\left(S_k,k\geqslant 1\right)$ is a non-negative sub-martingale and $(c_k,k\geqslant 1)$ a non-decreasing sequence of positive numbers, then for each $p\geqslant 1$: $$\mathbb P\left\{\max_{1\leqslant k\leqslant n}\frac{S_k}{c_k}\geqslant 1\right\}\leqslant \frac{\mathbb E\left[S_n^p\right]}{c_n^p}+\sum_{i=1}^{n-1}\left(\frac 1{c_i^p}-\frac 1{c_{i+1}^p}\right)\mathbb E\left[S_i^p\right].$$

Reference:

1 [Some Multivariate Chebyshev Inequalities with Extensions to Continuous Parameter Processes]1 Z. W. Birnbaum and Albert W. Marshall, Ann. Math. Statist. Volume 32, Number 3 (1961), 687-703.

Answer 2

You can do something with Talagrand's inequality for at least some normalizations. The simplest case would be if the $X_i$ are mean 0 and bounded, say $|X_i| \le 1$ almost surely, and you're looking at $\max_k S_k / \sqrt{k}$. In that case each $S_k / \sqrt{k}$ is a convex 1-Lipschitz function of $(X_1, \dotsc, X_n)$, and so $\max_k S_k/\sqrt{k}$ is a convex 1-Lipschitz function as well. Then Talagrand gives you $$ \mathbb{P} \left[\left| \max_{1 \le k \le n} \frac{S_k}{\sqrt{k}} - \mathbb{E}\max_{1 \le k \le n} \frac{S_k}{\sqrt{k}}\right| \ge \epsilon \right] \le C \exp[-c\epsilon^2]. $$ Of course you still need to bound that expectation. Maybe one can do better, but off the top of my head, using Talagrand again and a simple union bound, $$ \mathbb{E}\max_{1 \le k \le n} \frac{S_k}{\sqrt{k}} \le \mathbb{E}\max_{1 \le k \le n} \frac{|S_k|}{\sqrt{k}} \le C \sqrt{\log n}. $$

Answer 3

I am a beginner, I have a suggestion which is more or less confined to what I am reading presently. If you have access to Billingsley's "Convergence of Probability Measures" and if you are willing to compromise results to contains terms representing correlations eg. $E(S_i^{2}S_j^{2})$, you should have a look at Section $12$ of his book. He bounds $M_m : = \max_{i=1,\ldots,m} S_i$ with some other expressions like $M^{\prime}_m : = \max_{i=1}^{m}\min \{|S_i|, |S_m - S_i|\}$. Similarly he goes on to one term like $M^{\prime\prime}_{m}$. These bounds actually do come in use and improve bounds from $\frac{1}{\lambda^{2}}$ to $\frac{1}{\lambda^{4}}$ ($P(M_m \geq \lambda)$). Since Taligrand's bound already is exponential (for the bounded increments case), I do not know how this suggestion fits in. Davide might be able to suggest if this stuff is useful or not.

Answer 4

I can provide concentration inequality (which also reflect the size of the variance) around the mean of $max S_k/ sqrt(k)$ around its mean with a exponential decay. I assume that $X_i$ are centered Gaussian, this concentration inequality reflects a theorem due to Darling-Erdos (asserting that $max S_k/sqrt(k)$ recentred and renormalized converge to a Gumbel distribution). I'm currently looking for the logconcave case and the Rademacher case. Tell me if you are still interested, you can contact me if you want.

Kevin Tanguy