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?
-
$\begingroup$ 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.) $\endgroup$– Elle NajtMar 23, 2021 at 16:03
-
1$\begingroup$ Are the variables independent, at least? $\endgroup$– Igor RivinMar 23, 2021 at 16:17
-
$\begingroup$ @IgorRivin They are independent. Fixed. They are not identically distributed. $\endgroup$– Zach466920Mar 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.
-
$\begingroup$ Haha, maybe this is a bad direction. Do you think Monte-Carlo would be useful to look at? $\endgroup$ Mar 23, 2021 at 17:45
-
2$\begingroup$ 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." $\endgroup$ Mar 23, 2021 at 21:25
-