Distribution such that Expected Maximum is close to Expected Sum

67 Views Asked by At

For a distribution $\mathcal{D}$ on the nonnegative reals with expectation equal to 1, let $X_1$, $X_2$, $\ldots$, $X_n$ be $n$ independent samples. If we want to bound $\mathbb{E}[\max_i X_i]$, a classic technique is to write $$\mathbb{E}[\max_i X_i] \le \mathbb{E} \Big[\sum_i X_i \Big] = n.$$ In fact we can also show the factor $n$ here is tight; for example take $\mathcal{D}$ to be the distribution that takes value $1/\epsilon$ with probability $\epsilon$ and value $0$ with probability $1-\epsilon$; as $\epsilon$ goes to 0 we have that $\mathbb{E}[\max_i X_i] $ tends to $n$.

I am interested in knowing whether there is a nice way to classify the possible $\mathcal{D}$ that satisfy this property up to constants; specifically, we should have $$\mathbb{E}[\max_i X_i] = \Omega(n) .$$ More complicated constructions for $\mathcal{D}$ would also be interesting.

1

There are 1 best solutions below

4
On

Here is an answer that allows $n$ to vary and we look at asymptotics with $n$.

The $\Omega(n)$ property

For $X$ a nonnegative random variable with i.i.d. copies $\{X_i\}_{i=1}^{\infty}$, we say $X$ has the "$\Omega(n)$ property" if $E[\max[X_1, ..., X_n]] \geq \Omega(n)$, that is, if there is a constant $c>0$ such that: $$ E[\max[X_1,..., X_n]] \geq cn \quad \forall n \in \{1, 2, 3, ...\}$$

Asymptotics for finite $p$-moment

If there exists a $p>1$ such that $E[X^p]<\infty$ then it is impossible to satisfy the desired $\Omega(n)$ property because: \begin{array}{} E \left[\max_{i\in \{1, …, n\}} X_i\right] &\leq E\left[\left(\sum_{i=1}^n X_i^p\right)^{1/p}\right] \\ &\overset{(a)}{\leq} \left(\sum_{i=1}^n E[X_i^p]\right)^{1/p} \\&=(n E[X^p])^{1/p} \\& = O(n^{1/p}) \end{array} where (a) holds by Jensen's inequality for the concave function $f(y)=y^{1/p}$ defined on $y\geq 0$. For example, if the second moment is finite then the expectation of the max is at most $O(\sqrt{n})$.

Non-existence in general

Here is a proof of non-existence. Suppose $X$ is a nonnegative random variable with $E[X]=1$ such that the following holds: There is a $c>0$ such that
$$\int_{0}^{\infty} (1-P[X\leq x]^n)dx \geq cn \quad \forall n \in \{1, 2, 3, ...\}$$ We reach a contradiction.

We have $$ \int_0^{\infty} \frac{(1-P[X\leq x]^n)}{n}dx \geq c \quad \forall n \in \{1, 2, 3, ...\} \quad (Eq. 1)$$ Define the nonnegative functions $h_n(x) = \frac{(1-P[X\leq x]^n)}{n}$ for $x \geq 0$. We note that

1) $\lim_{n\rightarrow\infty} h_n(x)=0$ for all $x \geq 0$.

2) $\int_0^{\infty} h_1(x) =1$.

3) $h_n(x)\geq h_{n+1}(x)$ for all $x \geq 0$ and all $n \in \{1, 2, 3, ...\}$.

By the Lebesgue dominated convergence theorem we see that $h_n(x)$ is dominated by the (integrable) $h_1(x)$ and so: $$ \lim_{n\rightarrow\infty} \int_0^{\infty} h_n(x)dx = \int_0^{\infty} \lim_{n\rightarrow\infty} h_n(x)dx = 0$$ and this contradicts (Eq. 1).


The property 3 ($h_n(x)\geq h_{n+1}(x)$) holds as follows: Fix $x \geq 0$ and fix $n \in \{1, 2, 3, ...\}$. Define $p=P[X\leq x]$ and note that $p \in [0,1]$. We want to show: $$ \frac{1-p^n}{n} \geq \frac{1-p^{n+1}}{n+1} $$ Equivalently we want to show: $$ 1\geq (n+1)p^n - np^{n+1}$$ But the maximum of the function $(n+1)p^n-np^{n+1}$ over $p \in [0,1]$ is 1. $\Box$