The variance of the weighted median and optimal weights

Question

The median $\tilde{\mu}$ of a sample in many ways is analogous to the sample mean $\mu$. Both are an estimate for the population median or mean respectively, and both approach a Gaussian distribution for a large sample under certain conditions. It is known that the median asymptotically approaches a Gaussian distribution with variance $\sigma^2_{\tilde{\mu}}$ if the density $p(\tilde{\mu})$ is nonzero and continuously differentiable around the median (Rider 1960): \begin{align} \sigma^2_{\tilde{\mu}} = \frac{1}{4 N \left(p\left(\tilde{\mu}\right)\right)^2} \end{align} If the samples $x_i$ have the same mean but different variances $\sigma_i^2$, it can be shown that the inverse variance weighted sample mean ${_w\mu}$ is the estimate for the population mean with the lowest variance $\sigma^2_{_w\mu}$. \begin{align} {_w\mu} &= \frac{\sum_{i=1}^N w_i x_i }{\sum_{i=1}^N w_i}\\ w_i &= \sigma_i^{-2}\\ \sigma_{_w\mu}^2 &= \dfrac{1}{\sum_{i=1}^N w_i} \end{align} I am looking for an equivalent for the median. The weighted sample median ${_w\tilde{\mu}}$ is any value, which partitions the weights associated with values less than or equal and the weights of the values larger than or equal so their sums differ the least: \begin{align} {_w\tilde{\mu}} = \min_{_w\tilde{\mu}} \left| \left( \sum_{ \left\{ i | x_i \le _w\tilde{\mu} \right\} } w_i \right) - \left( \sum_{ \left\{ i | x_i \ge _w\tilde{\mu} \right\} } w_i \right) \right| \end{align} Now the question arises, what is the variance of the weighted sample median and how to set the weights optimally? I thought things like these must have been proven in the past a long time ago, but I was not able to find anything. I'd be thankful if you can help me find out more. This is how far I got on my own:

If samples have a different variance they must have come from a different distribution, so let's assume each sample is drawn from a different probability distribution $p_i$. Numerical experiments seem to indicate that in order to minimize the variance of the weighted median the weights should be set proportional to the density at the median of the distribution the sample was drawn from $p_i({_w\tilde{\mu}})$. This also makes a nice connection to inverse variance weights that are optimal for the weighted average, because in the weighted median, asymptotically each sample contributes a variance inversely proportional to the square of this density. Fig. 1: Relative weighting between samples following a Gaussian or uniform distribution with identical varianance each. The ratio of the Gausian density to the uniform density at the median is $\sqrt{\frac{6}{\pi}} \approx 1.38$ , this ratio is reached at around $0.58$ on the x-axis, coinciding with the minimum variance of the weighted sample median.

Fig. 2: The median of absolute deviations of the sample median of samples following either a gaussian, a Laplacian or a uniform distribution, with variances following an exponential distribution. The weights are set to a power of the associated sample variances and as can be seen the optimal power is around $0.5$.

When the weights are set equal to $p(\tilde{\mu})$ the variance of the median seems to approach: \begin{align} \sigma^2_{\tilde{\mu}} = \frac{1}{4 \left(\sum \left(p_i\left(\tilde{\mu}\right)\right)^2\right)} \end{align}

Rider 1960: https://www.tandfonline.com/doi/abs/10.1080/01621459.1960.10482056

Answer 1

The comments ask for a general approach to weighted medians. In the approach that makes sense to me, the weights end up the same as for weighted means.

The following result on means is a straightforward constrained optimization (e.g. here):

Suppose we have $n$ different methods of measuring the same quantity, and the sample mean $M_i$ from method $i$ has mean $\mu$ and variance $V_i$. Then the minimum-variance weighted average of those sample means is $$\frac{\sum M_i\, / \, V_i}{\sum 1 \, / \,V_i}$$

The sample medians, as asked about and pointed out in the question, have normal distributions. So a weighted average of sample medians will also be distributed normally. The variances will be proportional to the squares of the interquartile ranges, and minimizing the overall interquartile range will have the same result as minimizing the overall variance. This leads to the following result, parallel to the statement on means:

Suppose we have $n$ different methods of measuring the same quantity, and the sample median $M_i$ from method $i$ has median $\mu$ and interquartile range $r_i$. Then the minimum-interquartile-range weighted average of those sample medians is $$\frac{\sum M_i\, / \, r_i^2}{\sum 1\, / \, r_i^2}$$

If the goal is instead to take a weighted median of the samples (or of their sample median distributions), then we are looking for the mixture $R$ of the distributions $X_i$ (or of their sample median distributions) so that the sample median of $R$ has minimal variance.

Since the variance of the sample median of $R$ is inversely proportional to the pdf of $R$ at the median, we are looking for the mixture $R$ with highest possible pdf at that median. Assuming that all the $X_i$ have the same median (as in the post, and as in the case where they are all normal or all symmetric about the origin), the optimal mixture of $X_i$’s will be exclusively composed of the one $X_i$ which has the highest pdf at its median.

Answer 2

Assume all samples $x_i$ can follow a different probability distribution $p_i\left(x\right)$, otherwise different weighting would have only very limited application and the non-weighted median would almost always be the better choice. Consider a sorted list of weighted samples and the running sum of weights normalized by the sum of all weights. This computes the empirical cumulative distribution of the weighted mixture distribution, let the weighted cumulative distribution be ${_wP}\left(x\right)$. \begin{align*} {_wP}\left(x\right) = \dfrac{\left( \sum_i^N w_i \int_{-\infty}^x p_i\left(y\right) dy \right)}{\left( \sum_i^N w_i \right)} \end{align*} Now consider the sum of weights associated with samples less than or equal to the population median ${_p\tilde{\mu}}$, normalized by the sum of all weights, let it be $c$: \begin{align*} c = \dfrac{\left( \sum_{ \left\{ i | x_i \le {_p\tilde{\mu}} \right\} } w_i \right)}{\left( \sum_i^N w_i \right)} \end{align*} Without knowing the median of each distribution, each weight has probablity $^1/_2$ of being part of this sum or its counterpart. The variance introduced to the nominator by each weight is therefore $^1/_4$ the weights squared and the variance of $c$ is approximadted by the sum of individual variances divided by the normalization factor squared: \begin{align*} \sigma^2_c = \dfrac{\left(\sum_i^N w_i^2\right)}{4 \left( \sum_i^N w_i \right)^2} \end{align*} The weighted sample median ${_w\tilde{\mu}}$ is the sample where the empirical cumulative distribution reaches $^1/_2$. The expected value of $c$ is $^1/_2$ and its variance is the mean squared deviation between the empirical partitioning which determines the weighted sample median and the partitioning which would lead to the value closest to the weighted population median. Therefore the the inverse weighted cumulative distribution of $c$ is the same variance as the weighted median. Error propagation demands the derivative of ${_wP^{-1}}$ at $^1/_2$ which is inverse to the derivative of ${_wP}$ at the weighted population median. \begin{align*} \sigma^2_{_w\tilde{\mu}} &= \sigma^2_c \dfrac{d{_wP^{-1}}}{dx} \left(c\right)\\ \sigma^2_{_w\tilde{\mu}} &= \sigma^2_c \left(\dfrac{d{_wP}}{dx} \left({_w\mu}\right)\right)^{-1}\\ \sigma^2_{_w\tilde{\mu}} &= \dfrac{\left(\sum_i^N w_i^2\right)}{4 \left( \sum_i^N w_i \right)^2} \dfrac{\left( \sum_i^N w_i \right)^2}{\left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^2} \\ \sigma^2_{_w\tilde{\mu}} &= \dfrac{\left(\sum_i^N w_i^2\right)}{4 \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^2} \end{align*}

This is the variance we seek to minimize and a very similar optimization problem to the optimal weights for the weighted average. The weights that minimize the variance of the weighted median are reciprocal to the probability density of the sample distribution at the median, as can be shown taking the first and second derivatives with respect to the individual weights. The first derivative can only be zero for $w_i = p_i\left(\tilde{\mu}\right)$, the second derivative is positive: \begin{align*} \dfrac{d \sigma^2_{_w\tilde{\mu}}}{d w_j} &= \dfrac{ w_j \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right) - p_j\left(\tilde{\mu}\right) \left(\sum_i^N w_i^2\right)}{2 \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^3} \\%x/(2*(p*x+b)^2)-(p*(x^2+a))/(2*(p*x+b)^3) \dfrac{d^2 \sigma^2_{_w\tilde{\mu}}}{d^2 w_j} &= \dfrac{1}{2 \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^2} - \dfrac{2 w_j p_j\left(\tilde{\mu}\right)}{2 \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^3} + \dfrac{3 \left( p_j\left(\tilde{\mu}\right)\right)^2 \left(\sum_i^N w_i^2\right)}{2 \left( \sum_i^N w_i p_i\left(\tilde{\mu}\right)\right)^4} %1/(2*(p*x+b)^2)-(2*p*x)/(p*x+b)^3+(3*p^2*(x^2+a))/(2*(p*x+b)^4) \end{align*} \begin{align} \min_{w_i} \sigma^2_{_w\tilde{\mu}} = p_i\left({_p\tilde{\mu}}\right) \label{optimal_median_weights} \end{align} When the weights are set proportional to $p_i(\tilde{\mu})$, the variance of the median is equal to $1/4$ the inverse of the sum of probability densities at the median squared: \begin{align} \sigma^2_{_w\tilde{\mu}} &= \dfrac{1}{4 \left(\sum \left(p_i\left({_p\tilde{\mu}}\right)\right)^2\right)} \label{variance_of_weighted_median} \end{align} One unexpected consequence of weights proportional to the probability density at the median is that when the the distribution of each sample has the same shape, and only differs in scaling, the optimal weights are proportional to the inverse standard deviation, not inverse variances as for the weighted average. This is because a scaling by a factor amounts to a linear decrease of the density at the median, but an increase of the variance by the same factor squared.

Edit: Code and whitepaper: https://github.com/1ykos/weighed_median/blob/master/the_optimally_weighted_median_and_its_variance.pdf