I'm working on a problem where I need to calculate the median for a very large data set (for instance, 100M values) that has a log-normal distribution. Because of the data set's size, we were thinking about taking a sample (say, a random subset of 2000 values), and calculating its median. While this is much nicer from a computation perspective, I am very worried it will be inaccurate.

What method could I use to determine how accurate this sampled median is?

  • $\begingroup$ You can obtain the median using an online algorithm. If that's not good enough, search our site for additional approaches. Note that finding a median is a $O(N)$ algorithm and typically all the data need to be read at most twice, so $10^8$ is scarcely large: the median can be computed reliably in the amount of time it takes to read the data. $\endgroup$ – whuber Jan 30 '13 at 22:19

Just an empirical answer, I am sure someone else will be able to give you a more formal one.


# Generate a big dataset, log-normally distributed
bigdata <- rlnorm(10e6, meanlog=log(25))

# Now generate 500 different samples with 
# 10, 100, 1000, or 10000 elements in it
# and compare the medians

nelem <- c(10, 100, 1000, 10000)

m <- matrix(NA, nrow=1000, ncol=length(nelem))

for (el in 1:length(nelem))
  for (i in 1:500)
    data <- sample(bigdata, nelem[el], replace=F)
    m[i, el] <- median(data)

  # Plot the histogram
  hist(m, 100, col="black", freq=F, las=1, 
       main=paste(nelem[el],"element sampled"), xlab="Median")
  # Plot the "real" median
  abline(v=median(bigdata), col="red", lwd=2)

This gives you the distribution of the medians from 500 trials of sampling:

median histograms

As you can see, you get fairly good results already by sampling 1000 elements of the 10M from the original data.

  • $\begingroup$ +1 to @nico for providing a fully working empirical way to test different options. A very pragmatic way to test approaches, esp with the kind of tools most of us have at our disposal (R). I think the OP wants a confidence interval for his estimate of the median. $\endgroup$ – Ram Jan 30 '13 at 22:10

You could repeat the sampling process many times and calculate the confidence interval. This will give you an estimate where e.g. 95% of your sample medians fall.


Besides empirical answers, there are large sample ones:

If $f_0$ is the density (i.e. assuming a continuous variable) at the median then the variance of the median is asymptotically $\frac{1}{4nf_0^2}$

e.g. see http://en.wikipedia.org/wiki/Median#Variance


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.