# Distribution maximizing ratio of expected maximum over the mean

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.

• If $X_1, X_2,\cdots, X_n \sim_{iid} U([1 \cdots n])$ and $Y = \min(X_1, X_2, \cdots, X_n)$, There is a result showing $E[Y] = \Theta(\frac{\log(n)}{\log\log(n)}).$ I am not sure whether it will help to find the solution or not. N.B. This solution is used to calculate maximum number of collision in uniform hashing. May 1 at 1:31

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