3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ -1 because this looks like a homework problem (especially the second question). $\endgroup$ – Daniel Moskovich Dec 24 '09 at 0:36
  • $\begingroup$ Who assigns homework over Christmas break? $\endgroup$ – Greg Kuperberg Dec 24 '09 at 12:54
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.