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?
 A: 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.)
A: 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$.
A: 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}$.}$$
