# Maximum of a set of sums of iid random variables

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

• @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. – 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.)

• 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. – 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).

Proof:

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.

QED

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

• 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. – Tom LaGatta Jan 27 '11 at 18:45
• @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)$. .../... – Did Jan 27 '11 at 19:59
• .../... 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. – Did Jan 27 '11 at 20:10
• 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. – Tom LaGatta Jan 27 '11 at 20:20
• Guys, many many thanks. I'll read through these detailed answers and then respond. Thanks again :) – Pradipta Jan 27 '11 at 21:03