3
$\begingroup$

Suppose I have a set of $n$ real numbers, $\{x_1, x_2, \dots, x_n\}$.

I choose a uniformly random subset of size $m \le n$.

What is the expected maximum of the subset in terms of $n$, $m$ and $x_i$?

1 Answers 1

2

Let us assume $x_1 \leq x_2 \leq \cdots \leq x_n$.

With this ordering, note that the maximum of a $m$ element subset must be $\geq x_m$.

Total number of ways of choosing a $m$ element subset is $\dbinom{n}m$.

Out of these, $x_m$ is will be a maximum on $1$ occasion i.e. when the subset chosen is $\{x_1,x_2,\ldots,x_m\}$.

In general, $x_k$ will be a maximum on $\dbinom{k-1}{m-1}$. This is so since fixing $x_k$, the remaining $m-1$ $x_i$'s required to form the $m$ element set must all be less than or equals $x_k$ i.e. we need $i < k$. Hence, the number of ways to choose $m-1$ $x_i$'s such that $i < k$ is $\dbinom{k-1}{m-1}$.

Hence, the expected maximum of a $m$ element subset is $\dfrac{\displaystyle \sum_{k=m}^{n} \dbinom{k-1}{m-1} x_k}{\dbinom{n}{m}}$

  • 0
    @ByronSchmuland Oh Ok. Thanks. I just wanted to make sure that I was normal!2012-06-25