# Reference algorithm/formula for the distribution of the median of random variables?

The distribution of the mean of two random variables can be calculated using a convolution. I have a collection of $$n$$ independent random variables each with PDFs that are simple functions on $$[0,1]$$. I would like to know the exact distribution of the median of these variables. I understand there is a central limit theorem for the distribution of the sample median for i.i.d variables, but I don't have that assumption here. I also see that there's a way to get a formula for discrete random variables. Is there a reference for continuous random variables?

• The median is a particular order statistic, and there's a general formula here: en.wikipedia.org/wiki/… ... ah, but you don't have the iid assumption? (The link to the discrete case uses that assumption.) Mar 23, 2021 at 16:03
• Are the variables independent, at least? Mar 23, 2021 at 16:17
• @IgorRivin They are independent. Fixed. They are not identically distributed. Mar 23, 2021 at 17:22

## 1 Answer

Assuming the number of your random variables is $$2n,$$ the probability that the median is $$x$$ equals $$m(x)=\sum_{\mbox{subsets I of size n}}\prod_{i \in I} F_i(x) \prod_{j\notin I}(1-F_i(x),$$ where $$F_k$$ is the CDF of the $$k$$-th variable. Needless to say, for $$n$$ large (as in, bigger than about 6), this is not super useful. If the variables are $$i.i.d,$$ this is a fairly civilized formula.

• Haha, maybe this is a bad direction. Do you think Monte-Carlo would be useful to look at? Mar 23, 2021 at 17:45
• This suggests a dynamic programming approach for calculating this that is better than the naive sum: timvieira.github.io/blog/post/2021/03/18/… @Zach466920 "It turns out that we can evaluate the exponential-size sum in O(nk) time with a simple algorithm, which is essentially a probabilistic generalization of the dynamic program for evaluating the binomial coefficients. Furthermore, we can evaluate the distribution function for all n order statistics in O(n2) time. The code for doing this computation is below." Mar 23, 2021 at 21:25
• @LorenzoNajt Cool! Mar 23, 2021 at 21:38