Consider some probability distribution $D$ over non-negative reals with finite expectation $\mu$. Now for any positive $T$ consider sums of $T$ iid random variables drawn from $D$. A single sum of this sort would be $S(T) = \sum_{i = 1}^T x_i$ where each $x_i$ is a iid random sample from $D$.

We will consider $n$ such sums $S_1(T), S_2(T) \ldots S_n(T)$.

My question: Is it true that for any distribution $D$ and any finite positive $n$, there exists a finite positive $T$ (which may be a function of $n$ and $D$) such that $E(\max_{1 \leq j \leq n}S_j(T)) \leq 2 T \mu$?

This is true for, say, Bernoulli random variables, but I'd like to know the mildest condition under which a statement like this can be made. For example, is it true for all distributions with finite $4^{th}$ moments?


It is always true. Split $x_i=y_i+z_i$ where $y_i$ are bounded and $Ez_i\le \frac \mu{10n}$. You have no problems with $y_i$ because if they were alone,$ES_j$ would be concentrated in a very strong sense around $\nu T$ for large $T$ where $\nu=Ey_i\le\mu$ (see Didier's argument for details or recall the Bernstein inequality for exponential moments of sums of bounded variables). But you also have no problems with $z_i$ because even if you add them all up instead of taking the maximum at some point, you end up with mere $0.1 T\mu$.

| cite | improve this answer | |
  • $\begingroup$ @fedja Nice. To paraphrase (and check that I understood your argument), the factor $2$ may be replaced by $(1-.1/n)+.1$ "for every $.1$", hence by anything $>1$, and this holds as soon as the $x_i$ are i.i.d. and integrable. $\endgroup$ – Did Jan 27 '11 at 12:43

Let $M_n(T)=\max\{S_1(T),\ldots,S_n(T)\}$ where the $S_j(T)$ are i.i.d. and distributed like $S(T)$. A partial answer to your question is that $E(M_n(T))/T\to\mu$ when $T\to+\infty$ as soon as the function $K$ is integrable on $(0,+\infty)$, where $$ K(z)=\sup_TP(S(T)\ge zT). $$ Hence, if $E(x_1^{1+\varepsilon})$ is finite for a given positive $\varepsilon$, the inequality you are interested in holds and you can replace the factor $2$ in the RHS by any factor $>1$.

To see this, choose $u>1$ and note that $$ \mu T=E(S(T))\le E(M_n(T))=\int_0^{+\infty}P(M_n(T)\ge z)\mathrm{d}z\le\mu T(u+I^u_n(T)), $$ with $$ I^u_n(T)=\int_u^{+\infty}J_n^T(x)\mathrm{d}x,\qquad J_n^T(x)=P(M_n(T)\ge x\mu T). $$ Since the random variables $S_j(T)$ are i.i.d., $$ P(M_n(T)\ge z)=1-P(S(T)< z)^n, $$ hence $$ J_n^T(x)=1-(1-P(S(T)\ge x\mu T))^n. $$ The (weak) law of large numbers shows that $J_n^T(x)\to0$ for every $n\ge1$ and $x>1$, when $T\to+\infty$. Hence $I^u_n(T)\to0$ when $T\to+\infty$ as soon as a domination condition holds. Since $J_n^T(x)\le nP(S(T)\ge x\mu T)$, a sufficient condition is that the function $K$ defined above is integrable.

If $E(x_1^{1+\varepsilon})$ is finite, Markov inequality yields $P(S(T)\ge zT)\le E(S(T)^{1+\varepsilon})/(zT)^{1+\varepsilon}$ and $S(T)^{1+\varepsilon}\le T^\varepsilon (x_1^{1+\varepsilon}+\cdots+x_T^{1+\varepsilon})$ by convexity, hence one can choose $K(z)$ proportional to $1/z^{1+\varepsilon}$, which is integrable when $z\to\infty$.

(Note: a quantitative estimate claimed in a previous version is not as straightforward as I thought it was, so I deleted this part of my post. Sorry.)

| cite | improve this answer | |
  • $\begingroup$ Very nice. I'm curious about the quantitative bound as well, as it appears to mean that $T$ polynomial in $n$ suffices, which is really great. $\endgroup$ – Pradipta Jan 28 '11 at 16:11

Edit (Jan 28): As Didier points out in the comments, I made a mistake in my application of Chebyshev's inequality.

Didier and fedja already have gave you some great answers, but I'd like to go a little further. The reason all these arguments (including mine) are elementary is that $n$ is fixed, so it is tiny compared to $T$. Thus whether $n$ is $1$, finite, or even just growing very slowly compared to $T$, all the results will be qualitatively the same.

Suppose that the variables $X_i$ have finite variance $\sigma^2$, so that $$\mbox{$S(T)$ has mean $\mu T$ and standard deviation $\sigma \sqrt T$}.$$

In addition to the other answers controlling the expectation of the maximum, we can prove a stronger almost-sure result:

Theorem. Let $r > 1$ and $\epsilon > 0$. With probability one, there exists a (random) time $T_0$ so that for all $T \ge T_0$, $$ \max_{1 \le i \le n} S_i(T) \le \mu T + \epsilon T^{r/2}.$$

The proof is elementary, and only requires some basic theorems from probability (namely, Chebyshev's inequality and the Borel-Cantelli lemma).


Then $$ \mathbb P( \max S_i(T) \ge \mu T + \epsilon T^{r/2} ) = \mathbb P\left( \mbox{For some $i$, $S_i(T) \ge \mu T+ \epsilon T^{r/2}$} \right) $$ which equals $$\mathbb P\left( \bigcup_{i=1}^n \{S_i(T) \ge \mu T+ \epsilon T^{r/2}\} \right) \le n \cdot \mathbb P( S(T) \ge \mu T+ \epsilon T^{r/2})$$ by countable additivity. So it doesn't really matter that we're looking at the max of $n$ random variables or just a single one.

Now, let's analyze the right side of this expression using Chebyshev's inequality: $$n \cdot \mathbb P( S(T) - \mu(T) \ge \sigma ( \tfrac{\epsilon}{\sigma} T^{r/2} ) ) \le \tfrac{\sigma^2}{\epsilon^2} \frac{n}{T^r}.$$

Since $r > 1$ and $n$ is fixed, the sum $\sum \tfrac{n}{T^r}$ is convergent, so the Borel-Cantelli lemma implies that, with probability one, the event $\{\max S_i(T) \ge \mu T + \sigma T^{r/2}\}$ occurs for finitely many values of $T$. This completes the proof.


Some generalizations:

  • $n$ doesn't have to be finite. Suppose that $n = O(T^s)$. As long as $r - s > 1$, the series $\sum \tfrac{n(T)}{T^r}$ is still convergent, so the conclusion of the theorem still holds.

  • You can also modify the theorem above to the case that the variables $X_i$ have finite $(1+\epsilon)$th moment, for any $\epsilon$. Of course, the expression would change to $T^{r/(1+\epsilon)}$.

  • If you use the Central Limit Theorem, I believe that you can get the right side to be $\mu T + \sigma \sqrt T + O(\sqrt T)$. If you assume higher-than-second moment, the error term should be $o(\sqrt T)$.

  • The Law of the Iterated Logarithm gives an even better estimate. In your case, that should be: $$\mbox{With probability one, $\max_{1 \le i \le n} S_i(T) - \mu T \sim \sqrt{2 T \log \log T}$.}$$

| cite | improve this answer | |
  • $\begingroup$ By the way, you can prove results about expectations using the probability estimate $$\lim_{T \to \infty} \mathbb P( \max S_i(T) \ge \mu T + \epsilon T^{r/2}) = 0.$$ Try it as an exercise. $\endgroup$ – Tom LaGatta Jan 27 '11 at 18:45
  • $\begingroup$ @Tom Funny you would add this comment because, precisely, I felt a little skeptic about deducing asymptotic upper bounds of expectations from the almost sure results you recalled in your post... The only fact that $P(Y_T\ge c(T))=o(1)$ implies no control at all on $E(Y_T)$, hence at least some other properties of $(Y_T)$ than the convergence you mentioned in your comment, or quantitative estimates of $P(Y_T\ge c(T))$, would be necessary to deduce anthing about $E(Y_T)$. .../... $\endgroup$ – Did Jan 27 '11 at 19:59
  • $\begingroup$ .../... Four additional remarks. 1. In the proof you gave, it seems you forgot a factor $T$ in the numerator of Chebyshev's upper bound. 2. What is exactly the generalization to $1+\epsilon$ moments you want to describe is not clear to me. 3. The probability that $S(T)\ge\mu T+\sigma\sqrt{T}+o(\sqrt{T})$ cannot go to zero (precisely by the central limit theorem you invoke, the limit is $P(N\ge1)=.16...$, where $N$ is standard Gaussian). 4. What I like most in fedja's proof is precisely its minimal hypothesis: one does not need any higher-than-first moment. $\endgroup$ – Did Jan 27 '11 at 20:10
  • $\begingroup$ Didier, thanks for your comments. Now I too am skeptical about my claim. 1. Rats, you're right. That reduces the power of the theorem as I've stated it. Oh well. 2. The $1+\epsilon$ statement is that we don't need second moment, we can use Chebyshev's inequality with any moments. 3. You're right. 4. Agreed. I think fedja's proof is the slickest. $\endgroup$ – Tom LaGatta Jan 27 '11 at 20:20
  • $\begingroup$ Guys, many many thanks. I'll read through these detailed answers and then respond. Thanks again :) $\endgroup$ – Pradipta Jan 27 '11 at 21:03

Your Answer

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

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