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.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

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.