1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 1 at 1:31

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.