Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have $2k + 1$ points $a_1, ..., a_{2k+1}$. Each point is uniformly distributed between 0 and N. What is the distribution of the median (i.e. of the k+1-th point) ?

What happens if $a_1, ..., a_{2k+1}$ is a random set of $2k+1$ distinct points from $1, 2, ..., N$ ?

share|improve this question
    
-1 because this looks like a homework problem (especially the second question). –  Daniel Moskovich Dec 24 '09 at 0:36
    
Who assigns homework over Christmas break? –  Greg Kuperberg Dec 24 '09 at 12:54
add comment

2 Answers 2

I assume the points are meant to take integer values between $0$ and $N$.

The second question is easier. The probability that the median is $j$ is $$\binom{j}{k} \binom{N-j}{k} / \binom{N+1}{2k+1}.$$ (I hope I'm not answering homework here. If I am, remember that you need to justify this statement to get full marks.)

The probability that $j/N$ is between $x$ and $x+dx$ is roughly $$\frac{(2k+1)!}{(k!)^2} x^k (1-x)^k dx ,$$ as $N$ goes to infinity with $k$ fixed.

When you allow repetition, you should have the same asymptopics, but the problem is just messy enough that I can't get a simple answer. My best formula is

$$\frac{(2k+1)!}{(k!)^2} \frac{1}{(N+1)^{2k+1}} \int_{x=0}^1 (x+j)^k (N-j+x)^k dx.$$

Bounding the integral by the minimum and maximum values of the integrand gives reasonable bounds. I'll provide a proof if needed.

share|improve this answer
add comment

have you checked the "order statistics" article on Wikipedia.

share|improve this answer
add comment

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.