MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.