# Expected value of non-negative iid random variables

I want to show that, for $$n$$ iid non-negative random variables $$x_1, \dots, x_n$$, we have $$\mathbb{E} \max_{i \in [n]} x_i \lesssim (\mathbb{E} [x_i^{\log n}])^{\frac{1}{\log n }}.$$

I can only go so far as to show $$\mathbb{E} \max_{i \in [n]} x_i \leq n (\mathbb{E} [x_i^{\log n}])^{\frac{1}{\log n }}$$ for $$n \geq 3$$, using Jensen's inequality and the inequality $$\max_i x_i \leq \sum_i x_i$$, which seems a bit wasteful (and responsible for the factor of $$n$$).

Any tips for getting rid of the factor of $$n$$ would be greatly appreciated!

• You can only use Jensen's inequality if $\log(n) \geq 1$, so the inequality with the $n$-term will only hold for $n \geq 3$. Jan 21 at 19:22
• $\mathbb{E}\left[\max_{1 \le i \le n} x_i \right] \le \mathbb{E}\left[\left(\sum_i x_i^{\log n}\right)^{1/\log n}\right] \le \left(\mathbb{E}\left[\sum_i x_i^{\log n}\right]\right)^{1/\log n} = e\left(\mathbb{E}\left[x_i^{\log n}\right]\right)^{1/\log n}$, where the first inequality is obvious and the second uses Jensen. Is that wrong? Jan 22 at 9:38
• @mathworker21 That is the canonical argument, so should be posted as an answer. The constant $e$ is sharp. Jan 22 at 16:06

$$\mathbb{E}\left[\max_{1 \le i \le n} x_i \right] \le \mathbb{E}\left[\left(\sum_i x_i^{\log n}\right)^{1/\log n}\right] \le \left(\mathbb{E}\left[\sum_i x_i^{\log n}\right]\right)^{1/\log n} = e\cdot \left(\mathbb{E}\left[x_i^{\log n}\right]\right)^{1/\log n}$$

The first inequality is trivial, the second inequality is Jensen, and the equality uses $$n^{1/\log n} = e$$.

The canonical argument proving the upper bound is in the comment by Mathworker21, which has now been posted as an answer. I just want to add that the constant $$e$$ obtained there is sharp. Indeed, if $$\{X_i\}_{i=1}^n$$ are i.i.d. standard exponential variables, then $$E(\max_{1 \le i \le n} X_i)=\int_0^\infty P\Bigl(\max_{1 \le i \le n} X_i>t\Bigr) =\int_0^\infty[1- (1-e^{-t})^n] \, dt$$ $$=\int_0^1 \frac{(1-y)^n}{1-y}\, dy=\sum_{k=1}^n \frac{1}{k}=(1+o(1)) \log n$$ as $$n \to \infty$$. On the other hand, writing $$\ell:=\log n$$, by Stirling's formula we have $$E(X^\ell)=\int_0^\infty t^\ell e^{-t} \,dt=\Gamma(\ell+1)=(1+o(1))\sqrt{2\pi \ell} \,\Bigl(\frac{\ell}{e}\Bigr)^\ell\,,$$ so $$[E(X^\ell)]^{1/\ell}= (1+o(1))\,\Bigl(\frac{\log n}{e}\Bigr) \,.$$

Here is another proof that the constant factor $$e$$ in mathworker21's nice proof is the best possible.

Suppose that $$1-P(x_1=0)=P(x_1=1)=p:=p_n:=\dfrac{\ln n}n$$. Then $$E\max_{i\in[n]}x_i=1-(1-p)^n\ge1-e^{-np}=1-1/n\to1$$ and $$(Ex_1^{\ln n})^{1/\ln n}=p^{1/\ln n} =\exp\frac{\ln\ln n-\ln n}{\ln n} \to e^{-1}.$$ So, the constant factor $$e$$ is the best possible.

Let $$l:=E\max_{i\in[n]}x_i,\quad r:=(Ex_1^{\ln n})^{1/\ln n}.$$ Let $$q:=e r$$. Then for $$n\ge3$$ \begin{aligned} l&=\int_0^\infty P(\max_{i\in[n]}x_i>x)\,dx \\ &\le q+\int_q^\infty nP(x_1>x)\,dx \\ &\le q+\int_q^\infty n\frac{Ex_1^{\ln n}}{x^{\ln n}}\,dx \\ &= q+\int_q^\infty n\frac{r^{\ln n}}{x^{\ln n}}\,dx \\ &=e\Big(1+\frac1{\ln n-1}\Big)r \\ &\le Cr \end{aligned} for some universal real constant $$C>0$$. So, the factor $$n$$ has been removed, as desired.

• Why the downvote? This is a complete (and chronologically first) answer to the question. Of course, kudos to mathworker21, who later found a better proof, with a slightly better bound. But downvoting this answer seems unfair. Jan 30 at 14:33