Sample $k$ of $n$ numbers (with replacement), what is the probability for a certain from the $n$ numbers to be the median of the $k$ numbers

Question

Suppose we have ordered numbers $a_1 < a_2 < \dots < a_n$. Now we sample $k$ of them with equal probability and with replacement and compute the median of these and call it $m$. (Let us assume that $k$ is odd for the sake of simplicity.) What is the probability the $m = a_i$ for each $i$?

I want to know this to construct the probability mass function for the median of $k$ random draws from a sample of $n$ numbers.

Answer 1

If $m$ is the median of $k$ samples, and $u$ is the number of samples $\le m$, then

$$P(m \le a_i) = \frac{1}{n^k}\sum_{u=(k+1)/2}^k \binom{k}{u}\, i^u\, (n-i)^{k-u}$$ $$P(m = a_i) = P(m \le a_i) - P(m \le a_{i-1})$$

$$\ $$ A good test case is $n=4, i=2, k=3$ for which we can list the relevant cases.

The median is 1 if the samples are the

• 1 permutation of 111
• 3 permuations of 112
• 3 permutations of 113
• 3 permutations of 114

for a total probability of 10/64, which agrees with the formula.

The median is 2 if the samples are the

• 3 permutations of 122
• 6 permutations of 123
• 6 permutations of 124
• 1 permutation of 222
• 3 permutations of 223
• 3 permutations of 224

for a total probability of 22/64, which also agrees with the formula.