An Upper Bound for the Average of Top Order Statistics - MathOverflow

An Upper Bound for the Average of Top Order Statistics

2010-10-20T18:40:54Z

The following problem arises when we try to bound the expected offline optimal value of a simple online assignment problem with random values and unit weights, by its deterministic approximation.

The Problem

Consider a sequence $\{X_i\}_{i=1}^n$ of non-negative integrable i.i.d. random variables with absolutely continuous c.d.f. $F(x)$ . Let $X_{(i)}$ be the $i^{\rm th}$ order statistics, so that $X_{(1)}$ is the minimum of the sequence and $X_{(n)}$ is the maximum. Now, let $T_k$ be the average of the top $k^{\rm th}$ order statistics, that is, $T_k = \frac 1 k \sum_{i=n-k+1}^n X_{(i)}$ . We would like to show that the expected value of the average of the top order statistics is upper bounded as follows

$$\mathbb{E} T_{k} \le \mathbb{E} \left[ X | F(X) \ge 1 - k/n \right],$$

where the right hand size is the conditional expectation of X given that it is larger than the $(1-k/n)$ -percentile. In order to keep things simple, we may assume that the c.d.f. $F(\cdot)$ is strictly increasing in its domain.

Moreover, we may we fix $\rho \in (0,1)$ , and set $k=[\rho n]$ ; so that we are interested in the average of the top $\rho$ fraction of the sequence. If we scale both $n$ and $k$ to infinity while keeping the ratio $\rho$ fixed, it seems to be the case that the bound is asymptotically tight:

$$ \lim_{n \rightarrow \infty} \mathbb{E} T_{[\rho n]} = \mathbb{E} \left[ X | F(X) \ge 1 - \rho \right]. $$

Can you show if these results hold? I have done some numerical experiments with a couple of distributions (uniform, truncated normal, exponential) that confirm these results. Any help or pointer would be appreciated.

Thanks in advance.

More motivation

This is a stripped down version of a more complicated problem. Suppose that we have an incoming inventory of $n$ different items with unknown value arriving in an online fashion. We can only keep $k$ items of the $n$ total. The decision to keep an item has to be made at the moment of arrival, and once we decide to keep an item we need to stick to this decision.

The value of i-th item, denoted by $X_i$ , is unknown, and revealed when it arrives (before a decision needs to be made). However, we do have a prior for the values; they are drawn independently from an identical distribution $F(\cdot)$ . The objective of the problem is designing an online policy that maximizes the expected total value of the assignment.

A useful benchmark, when comparing online policies, is the offline optimal solution. Given a realization of the values $X=\{X_i\}_{i=1}^n$ , the optimal value of the offline problem, denoted by $P(X)$ , is
\begin{align} P(X) = \max_y &\; \sum_{i=1}^n y_i X_i \\ \text{s.t.} & \sum_{i=1}^n y_i = k, \\ & y_i \in \{0,1\} \end{align} In this simple case, the offline optimal solution is to keep the items with the k-th highest values. Equivalently, we have that $P(X) = \sum_{i=n-k+1}^n X_{(i)}$ . We are interested in the expected optimal value of offline optimal solution, which is given by $\mathbb{E} P(X) = k \mathbb{E} T_k$ .

A simple online policy could instruct us to keep those items with value larger than the $(1-k/n)$ -percentile. Such policy can be shown to attain an expected value of $n \mathbb{E} \left[ X \mathbf{1} \{ F(X) \ge 1 - k/n\} \right]$ when $n$ is large.

The results that we want to prove would allows us to upper bound the expected optimal value of the offline problem by a bound that could be attained, asymptotically, by an online policy. This would confirm that our policy is good.

Answer by jat for An Upper Bound for the Average of Top Order Statistics

2010-10-22T07:31:08Z

There's a variational principle, attributed to Ky Fan, that provides an alternative description of the sum of the $k$ largest numbers in a nonnegative sequence: $$ \frac{1}{k} \sum_{i=1}^k x^\circ_i = \inf_{x = y+ z} \ \Vert y \Vert_\infty + \frac{1}{k} \Vert z \Vert_1 $$ The infimum is attained by a 1-parameter family (sometimes I get this backward, so check it!): $$ y_i = \begin{cases} x_i, & x_i \leq t \newline t, & \text{else} \end{cases} \quad\text{and}\quad z_i = \begin{cases} x_i - t, & x_i > t \newline 0, & \text{else} \end{cases} $$ Then the infimum occurs over $t > 0$. The advantage of this formulation for your problem is that you can draw the expectation inside the infimum, compute the expectation (which is easy), and then take the infimum. You should get the value you noted above.

Answer by zhoraster for An Upper Bound for the Average of Top Order Statistics

2010-10-22T10:23:43Z

Write $$ E[T_k]=E[E[T_k|X_{(n-k)}]] $$ The distribution of $X_{(n-k+1)},\dots,X_{(n)}$ given $X_{(n-k)}=x$ is the same as the conditional distribution of a monotone arrangement of $n-k$ independent r.v.'s with cdf $F$ given they all are not less than $x$. (This can be proved easily e.g. by using the quantile transform.)

Now the mean value of monotone arrangement of a sequence is equal to the mean value of the sequence itself. So by linearity of conditional expectation we can write $$ E[E[T_k|X_{(n-k)}]]=E[E[X|X\ge X_{(n-k)}]], $$ where $X$ is an independent of $X_{(n-k)}$ r.v. with cdf $F$.

Now it is again about the quantile transform. Let $U=F(X)$, $U_{(n-k)}=F(X_{(n-k)})$. We have (by the independence of $U$ and $U_{(n-k)}$) $$ E[X|X\ge X_{(n-k)}]=E[F^{(-1)}(U)|U>U_{(n-k)}] = \frac{1}{1-U_{(n-k)}}\phi(U_{(n-k)}), $$ where $\phi(u) = \int_u^1 F^{(-1)}(x)dx$. But we do know the density of $U_{(n-k)}$, so the expectation of this expression is equal to $$ \frac{n!}{(n-k-1)k!}\int_0^1 u^{n-k-1}(1-u)^{k-1}\phi(u)du = \frac{n}{k}E[\phi(B)], $$ where $B$ has $\mathrm{Beta}(n-k,k)$ distribution. But $\phi(x)$ is easily seen to be concave, so by Jensen's inequality $E[\phi(B)]\le \phi(E[B]) = \phi(1-k/n)$, as required.