Return to Answer

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.

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

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}

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.