I like that notion of robustness! I’m having trouble understanding the big-O behavior here because of the 1/N^2 term—does the decreasing nature of this function as N goes up mean the mean becomes more robust than the median for large N, or does the median always win for any N?
There’s a 1/3rd chance that the median does not change under an infinitesimal perturbation as I’ve defined it. There’s a Θ(N−1/2) chance that the mean does not change under an infinitesimal perturbation as I’ve defined it.
Or, to flip it around:
There’s a 2/3rds chance that the median does change under an infinitesimal perturbation as I’ve defined it. There’s a 1−Θ(N−1/2) chance that the mean does change under an infinitesimal perturbation as I’ve defined it.
As you increase the number of data points, the mean asymptotes towards ‘almost always’ changing under an infinitesimal perturbation, whereas the median stays at a 2/3rds[1] chance.
Minor self-nit: this was assuming an odd number of data points. That being said, the probability assuming an even number of data points (and hence mean-of-center-two-elements) actually works out to the same - {−ϵ,−ϵ},{−ϵ,0},{0,−ϵ},{0,ϵ},{ϵ,0},{ϵ,ϵ} all change the median, or 6⁄9 possibilities.
I like that notion of robustness! I’m having trouble understanding the big-O behavior here because of the 1/N^2 term—does the decreasing nature of this function as N goes up mean the mean becomes more robust than the median for large N, or does the median always win for any N?
Ah, to be clear:
There’s a 1/3rd chance that the median does not change under an infinitesimal perturbation as I’ve defined it.
There’s a Θ(N−1/2) chance that the mean does not change under an infinitesimal perturbation as I’ve defined it.
Or, to flip it around:
There’s a 2/3rds chance that the median does change under an infinitesimal perturbation as I’ve defined it.
There’s a 1−Θ(N−1/2) chance that the mean does change under an infinitesimal perturbation as I’ve defined it.
As you increase the number of data points, the mean asymptotes towards ‘almost always’ changing under an infinitesimal perturbation, whereas the median stays at a 2/3rds[1] chance.
Minor self-nit: this was assuming an odd number of data points. That being said, the probability assuming an even number of data points (and hence mean-of-center-two-elements) actually works out to the same - {−ϵ,−ϵ},{−ϵ,0},{0,−ϵ},{0,ϵ},{ϵ,0},{ϵ,ϵ} all change the median, or 6⁄9 possibilities.
Gotcha—thanks.