18
$\begingroup$

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.

$\endgroup$

4 Answers 4

11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I didn't know about this generalization of the Hajek-Renyi inequality. I need to think about it to see if it can be generalized further with exponential functions. $\endgroup$
    – Adrien
    Oct 31, 2013 at 10:17
  • 1
    $\begingroup$ Should the $c_n^p$ on the right-hand side be in the denominator? It seems that if we scale the $S_k$ down by a larger factor, the probability that they exceed some value should decrease rather than increase. I would check the paper, but it doesn't seem to have a Theorem 1, so I'm not really sure. $\endgroup$ Sep 24, 2019 at 8:41
  • $\begingroup$ Concerning only the second term, it seems that if all $\mathbb E[S_i^2]=i$, we need $c_i^2\approx i \log i$ to get a probability below 1. This seems similar to the answer of @Mark, but worse than the $\sqrt{\log\log n}$ answer by Tanguy. (Just for my own understanding and comparison) $\endgroup$ Sep 24, 2019 at 8:48
  • 1
    $\begingroup$ Indeed, there was a typo. The proofs works in the same way as for Doob's inequality. I also made the reference more precise. $\endgroup$ Sep 24, 2019 at 8:49
7
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ (this concentration inequality is purely non asymptotic and improve as $n$ goes to infinity). $\endgroup$ Nov 18, 2015 at 14:42
  • $\begingroup$ This basically says $\sup_{k\le n}\frac{\max S_k}{\sqrt{k}}\approx \sqrt{\log\log n}$. Very nice! $\endgroup$ Sep 24, 2019 at 8:25

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.