5
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Tardis
    Jan 21 at 19:22
  • 4
    $\begingroup$ $\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? $\endgroup$ Jan 22 at 9:38
  • $\begingroup$ @mathworker21 That is the canonical argument, so should be posted as an answer. The constant $e$ is sharp. $\endgroup$ Jan 22 at 16:06

4 Answers 4

11
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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) \,.$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 30 at 14:33

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.