Maximum of a set of sums of iid random variables

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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