Assume we have a large, but finite population $u_1,\ldots,u_N$, and we try to estimate its median by looking at only $k$ samples the population (say $k=2t+1$ is a small odd integer).

A folklore theorem seems to be that the best you can do is draw $k$ samples without replacement from the population and compute the sample median.

An obvious alternative would be to sample with replacement, which might appear natural since then the outcomes are independent.

How can we formally argue that the quality of the median estimator when sampling without replacement is strictly better than when sampling with replacement?

I wrote down the probability that of the sample median is the $i$th smallest of the $N$ values. For sampling without replacement, this is a hypergeometric distribution $$p_i = \frac{\binom{i-1}{t}\binom{n-i}{t}}{\binom{n}{2t+1}},$$ for sampling with replacement it is an order statistic from a discrete parent $$ p_i' = \frac{1}{\mathrm B(t+1,t+1)} \int_{\frac{i-1}n}^{\frac in}u^t(1-u)^t du\,,$$ where $\mathrm B$ is the beta function.

If you plot the two for fixed values of $n$ and $t$, the $p_i$ look more concentrated than the $p_i'$, but don't know a nice proof of the general statement.


1 Answer 1


If you know the population size $N,$ the sample with replacement can be simulated using a sample without replacement: they can be coupled such that the former has a known distribution conditioned on the latter. And if you can simulate a distribution yourself, that distribution doesn't tell you anything new about the parameters.

By definition, if an estimate $f_1(X)$ minimizes some expected error $\mathbb E[L(f_1(X))]$ given $X,$ then any other estimate gives a larger or equal expected error. By monotonicity of expectation, an estimate of the form $f_2(X,I),$ where $I$ is an independent ancillary variable (i.e. doesn't depend on $a_1,\dots,a_N$) will give a larger or equal expected error.

Consider independent samples $X_1,X_2,\dots.$ Taking the first $k$ gives a sample with replacement. Taking the first $k$ distinct values $X_{i_1},\dots,X_{i_k}$ gives a sample without replacement. The distribution of $(X_1,\dots,X_k)$ given $(X_{i_1},\dots,X_{i_k})$ does not depend on the population; there is a coupling such that $(X_1,\dots,X_k)$ is a function of $(X_{i_1},\dots,X_{i_k})$ and an ancillary multinomial variable.

So the important thing is to see if there is a precise sense in which the sample median $X_{(t+1)}$ is optimal for this problem. You mentioned you had tried to calculate some information about ranks. Let $R_{(i)}$ denote the rank of $X_{(i)}$ within the population, so it's a value in $1,\dots,N.$

One property is that $j=t+1$ minimizes the expected difference in rank $\mathbb E|R_{(j)}-\tfrac{N+1}2|.$ To see this, use the symmetry of reversing the range $R_{(j)},\dots,R_{(2t+2-j)}$ by defining $R'_{(i)}=R_{(2t+2-j)}+R_{(j)}-R_{(2t+2-i)}$ for $j\leq i\leq 2t+2-j$ and $R'_{(i)}=R_{(i)}$ otherwise. This gives a random variable $R'$ with the same distribution as $R.$ But $$|R_{(j)}-\tfrac{N+1}2|+|R_{(2t+2-j)}-\tfrac{N+1}2|\geq |R_{(t+1)}-\tfrac{N+1}2|+|R'_{(t+1)}-\tfrac{N+1}2|$$ by convexity of absolute value; it's an inequality of the form $|x|+|y|\geq |x+t|+|y-t|$ for $x<y$ and $0<t<y-x.$ By symmetry, the two terms on the left hand size have the same distribution, and the two terms of the right hand side have the same distribution, which gives $\mathbb E|R_{(j)}-\tfrac{N+1}2|\geq \mathbb E|R_{(t+1)}-\tfrac{N+1}2|.$

By considering the translation and reversal symmetry of $R_{(1)}$ and $R_{(2t+1)}$ it is possible to show stochastic domination, i.e. $\mathbb E[L(|R_{(j)}-\tfrac{N+1}2|)]\geq \mathbb E[L(|R_{(t+1)}-\tfrac{N+1}2|)]$ for any non-decreasing function $L,$ with strict inequality for $j\neq t+1$ if $L$ is strictly increasing.

  • $\begingroup$ Could you elaborate on "By monotonicity of expectation, an estimate of the form f2(X,I) I is an independent ancillary variable (i.e. doesn't depend on a1,…,aNa1,…,aN) will give a larger or equal expected error."? I currently don't see why the expected error can't go down by including I? $\endgroup$
    – Sebastian
    Oct 29, 2017 at 3:18
  • $\begingroup$ @Sebastian: possibly. That statement has very strong assumptions - $I$ is independent of $X$ and of the parameters, and $f_1$ is assumed to be optimal. So $\mathbb E[f_2(X,I);\theta]=\mathbb E[f_2(X,I)|I;\theta]\geq \mathbb E[f_1(X);\theta].$ In fact here $I$ is discrete, so this is saying that the weighted sum $\sum_i E[f_2(X,i)]p(i),$ must be at least $\mathbb E[f_1(X)].$ $\endgroup$
    – Dap
    Oct 29, 2017 at 7:55
  • $\begingroup$ Thanks, that makes sense. $\endgroup$
    – Sebastian
    Oct 29, 2017 at 16:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .