Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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}}$$

share|improve this answer
    
And this expression simplifies nicely when the set is $\{1,2,\dots,n\}$: math.stackexchange.com/questions/65398/… –  Byron Schmuland Jun 25 '12 at 22:59
    
@ByronSchmuland Just to make sure I am not imagining things didn't you make the same comment to this post around $10$ minutes back? I find that the timestamp says $1$ minute ago instead of $10$ minutes ago. –  user17762 Jun 25 '12 at 23:03
    
Yes I deleted and re-commented to correct a typo $m\to n$. –  Byron Schmuland Jun 25 '12 at 23:04
    
@ByronSchmuland Oh Ok. Thanks. I just wanted to make sure that I was normal! –  user17762 Jun 25 '12 at 23:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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