Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

One can use Birnbaum and Marshall inequality:

Theorem(1). If $(S_k,k\geqslant 1)$ 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 c_n^p\mathbb E[S_n^p]+\sum_{i=1}^{n-1}\left(\frac 1{c_i^p}-\frac 1{c_{i+1}^p}\right)\mathbb E[S_i^p].$$

Reference:

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

share|improve this answer
    
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. –  Adrien Oct 31 '13 at 10:17
    
Btw a few typos: "sequence sequence", $c_k$ should be non-decreasing, and it should be $\frac{1}{c^{p}_{n}}$ I guess. –  Adrien Oct 31 '13 at 10:19
    
@Adrien I corrected the typos, thanks. –  Davide Giraudo Oct 31 '13 at 10:51

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.