A median of a weighted probability distribution. With positive weights summing to one, at most half the weight lies strictly below a weighted median and at most half lies strictly above it. The lower weighted median chooses the first observed value whose cumulative weight reaches one half; the convention matters when the cumulative mass is exactly one half.
For ordered distinct values with positive weights summing to one, choose the first value whose cumulative weight reaches one half. The preceding cumulative weight is strictly below one half, and the remaining mass is at most one half, proving the displayed conditions. Stopping on equality chooses the lower value when a cumulative weight is exactly one half. Sorting followed by a scan takes time; median of medians partitioning with a residual weight target gives deterministic linear time.
Articles by others on the same topic
The weighted median is a statistical measure that extends the concept of a median by incorporating weights assigned to each data point. In a standard median calculation, the values are simply ordered and the median is the middle value (or the average of the two middle values in the case of an even number of observations). In contrast, the weighted median accounts for the relative importance of each data point through its associated weight.