# Median-of-k elements

Hello,

Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$. Then out of theses $k$ elements, I find the median (i.e. the $\lceil \frac{k}{2} \rceil$'s smallest element). I need to find the probability that this chosen median is the i'th smallest element in the original sequence.

I am thinking about it as follows. First I need to pick the i'th smallest element (call it $x_i$), which has a probability of $\frac{1}{n}$. Then I am left with picking $\lfloor \frac{k}{2} \rfloor$ elements $< x_i$ and $\lfloor \frac{k}{2} \rfloor$ elements $> x_i$. It is clear that we have $i-1$ elements $< x_i$ and $n-i$ elements $> x_i$.

So what I thought is that the probability for selecting the elements $< x_i$ is : $${i-1 \choose \lfloor \frac{k}{2} \rfloor} \Pi_{j=0}^{\lfloor \frac{k}{2} \rfloor -1} \frac{1}{i-1-j}$$

And I approach choosing the rest of elements in a similar way. I don't know if I am complicating the problem too much or my entire way of thinking is wrong. So any help is highly appreciated.

## 1 Answer

Your final expression is too complicated, and the previous paragraph is all that you need.

The probability that the $i$th element is the sample median is $${i-1 \choose \lfloor k/2 \rfloor}{n-i \choose \lfloor k/2 \rfloor} \left/ {n \choose k } \right. .$$