[Math] Calculating new median if one of the observations from original calculation is removed

arithmeticmedian

find new average if removing one element from current average

Hey guys, found an old question that I would like to build on if possible, would appreciate your help.

To piggyback on this old question I found…Is it possible to find calculate a median by removing one number from the current median?

Let's say all you have is the median of a set of numbers (e.g., $= 40$) and the number of observation (e.g., $= 100$), and want to find the new median if one of the observations was removed (e.g., $= 50$)?

Going back and recalculating the median without the focal observation is not an option.

Thanks, J

Best Answer

Sure. You have $n$ observations $x_i$ which are sorted. Say $n$ was even, then the median after deleting $x_j$ is the $n/2$th observation among those which are left. This is just the $n/2$th of the original observations if that is less than $j$, otherwise it is the $(n+2)/2$th of the original observations. You can proceed similarly if $n$ was odd.

The tricky aspect here is: if you keep on doing this, when do you actually update the data structure rather than continuing to modify your accessor function?

One difference from the case of the mean is that it actually doesn't really matter what the old median was or even what the removed value was, all that matters is where the removed value was in the sorted sequence.

That said, if all you have is the old median and the deleted observation, then no, you cannot know the new median in general. All you can be sure is that the median could only increase (resp. decrease) if the deleted observation was smaller (resp. larger) than the old median.

Related Solutions

[Math] Calculating the median in the St. Petersburg paradox

Feller was able to determine the median asymptotically, namely $N \log_2 N$, or $\log_2 N$ per game. He actually proved an even stronger concentration bound. This result can also be found in his "Introduction to Probability".

Economists are still coming up with new interpretations of this problem, known as the St. Petersburg Paradox, after the city in which Euler, who invented it, was working (the name might be due to Feller). See, for example, this article, which also suggests the same value.

[Math] Algorithm to separate an array of numbers into “low”, “medium” and “high” ranges

It's a little bit unclear what you want, so I'm going to present several possible answers that you can choose from.

The simplest possibility is that you simply want to divide the range into three equal parts. Assuming that the lowest number is $L$ and the highest is $H$, you can calculate the ranges as:
1. from $L$ to $L + \frac{H-L}3$,
2. from $L + \frac{H-L}3$ to $L + 2\frac{H-L}3$ and
3. from $L + 2\frac{H-L}3$ to $H$.
In fact, a simple way to assign a number $n$ into one of these ranges is to subtract $L$ from it, multiply the result by $3$, divide it by $H-L$ and truncate it to the next lowest integer:
```
group = int( (n - L) * 3 / (H - L) );
```
This will give you a number from $0$ to $2$, or possibly $3$ if $n = H$. To avoid that last case, you can either replace $H$ in the formula with $H+1$ (if working with integers) or $H + \epsilon$ for some very small number $\epsilon$ (if working with floats), or just check for it afterwards, e.g.:
```
if (group > 2) group = 2;
```
Obviously, you can use the exact same method for more groups than 3 as well.
Another possibility is that you want to divide the numbers into three groups of equal size, such that all numbers in group 1 are less than or equal to those in group 2, which are less than or equal to those in group 3. In other words, you want to divide your numbers into three quantiles.

The simplest way to do this programmatically is just to sort your list of numbers, and then split the sorted list into three parts of (approximately) equal length. In pseudocode, using Python-like array slice notation:
```
list.sort();
n = list.length;
part1 = list[0 : n/3];
part2 = list[n/3 : 2*n/3];
part3 = list[2*n/3 : n];
```

Best Answer

Related Solutions

[Math] Calculating the median in the St. Petersburg paradox

[Math] Algorithm to separate an array of numbers into “low”, “medium” and “high” ranges

Related Question