Distribution maximizing ratio of expected maximum over the mean

Question

I’m looking for a distribution that is non-negative, or has good tail bounds (so non-negative with high probability) and maximizes the ratio between the expected maximum of $n$ iid samples and the mean.

That is, if $X_1,\ldots,X_n$ are iid samples from the distribution, $Y = \max(X_1,\ldots,X_n)$, and $X$ is another sample, then I want to maximize $$\frac{E[Y]}{E[X]}.$$

For instance, for a normal distribution $N(\mu,\sigma^2)$, $E[Y]$ is $\Theta(\sigma\sqrt{\log n})$, however for the samples to be non-negative with high probability, because of the tail bound on normal distribution, $\mu$ should grow faster than $\sigma$, so $\frac{E[Y]}{ E[X]}$ will be bounded by $O(\sqrt{\log n})$.

On the other hand, if I’m not mistaken, we can have $\frac{E[Y]}{ E[X]} = \Theta(\frac{\log n}{\log\log n})$ through binomials, a balls and bins problem setting. However I’m not sure if this is the largest that $\frac{E[Y]}{ E[X]}$ can be.

Answer 1

For non-negative random variables, the answer is $\Theta(n)$.

Notice that $Y \leq X_1 + \cdots + X_n$, and so $E[Y] \leq n E[X]$.

In the other direction, consider the following random variable: $X = 1$ w.p. $1 - 1/n$, and $X = n$ otherwise. On the one hand, $E[X] = 1 - 1/n + n/n \approx 2$. On the other hand, $\Pr[Y = 1] = (1-1/n)^n \approx 1/e$, and so $E[Y] \approx 1/e + (1-1/e) n \approx (1-1/e) n$. In total, $E[Y]/E[X] \approx \frac{e-1}{2e} n$.