# Median-of-k elements

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.

-

There are a total of $n\choose k$ choices possible and ${i-1\choose \frac{k-1}2}{n-i\choose\frac{k-1}2}$ lead to success. Thus the answer can be given as simply $$\frac{ {i-1\choose \frac{k-1}2}{n-i\choose\frac{k-1}2}}{n\choose k}.$$