3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @Santiago: Could you tell me more about the assignment problem you are working on? (This isn't relevant to your question, but I've also done some work on expected values of random assignment problems and so am interested from that standpoint.) $\endgroup$ Oct 20, 2010 at 20:02
  • $\begingroup$ @Mike: Sure Mike, let me update the question with more information. $\endgroup$
    – Santiago
    Oct 20, 2010 at 20:57
  • $\begingroup$ I think I have a solution, I will add it when I have time (within an hour or two). $\endgroup$
    – zhoraster
    Oct 22, 2010 at 8:00

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ An addition. The asymptotical tightness is also true. If we set $k\approx \rho n$, then $\mathrm{Beta}(n-k,k) = \mathrm{Beta}((1-\rho)n,\rho n)\to 1-\rho$, $n\to\infty$. So we get $E[T_k(n)]\to \frac{1}{\rho}\phi(1-\rho)$, as expected. Moreover, as I've told above, $T_k$ given $X_{(n-k)}$ has nice distribution, so we're able to apply LLN here (though some extra work is needed) to get $T_k(n)\to \phi(1-\rho)/\rho$. It might be even possible to get a (non-central) limit theorem here. $\endgroup$
    – zhoraster
    Oct 22, 2010 at 13:44
  • $\begingroup$ @zhoraster: Great work! Surprisingly, I was working on a solution along the same lines. I just discovered the result about the conditional distribution on X_(n-k) in Section 6.5 of "Order statistics" by H.A.David, and H.N.Nagaraja. I am going to check your result and will let you known ASAP. This looks promising! Thanks again! $\endgroup$
    – Santiago
    Oct 22, 2010 at 20:04
  • $\begingroup$ @Santiago: You're quite welcome. In fact, you conjecture was nice. And fortunately, correct :) $\endgroup$
    – zhoraster
    Oct 22, 2010 at 21:15
  • $\begingroup$ @zhoraster: Your answer is perfect. Congratulations! It is really a nice problem, with an elegant solution. I enjoyed reading your answer. Bests. $\endgroup$
    – Santiago
    Oct 23, 2010 at 0:00
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @jat: Thanks very much for your solution. I am not familiar with this approach, but looks very interesting. I will look it in detail and will let you know! Thanks! $\endgroup$
    – Santiago
    Oct 22, 2010 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.