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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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