2 added 1920 characters in body

## Moremotivation

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 \\& \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.

1

# An Upper Bound for the Average of Top Order Statistics

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.

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.