Re:Find running median from a stream of integers
by mturmon on Monday May 21, 2012 @10:16PM
(#4005963)
You're right, it's kind of asking the wrong question.
Because of the robustness properties of the median, it would be hard to argue that the first 1E6 samples weren't enough, and that you really need to hang on for the next 9E6 to get an accurate median.
In real problems, if you have that much data, you would more likely start to question the iid assumption anyway, and you'd start looking for drifts in the medians within sliding windows. Real problems being real problems, you'd probably find some drift, and this would point out the unhelpfulness of an "all-data" median. ("Since the data is drifting, what is this the median of?")
Because of the robustness properties of the median, it would be hard to argue that the first 1E6 samples weren't enough, and that you really need to hang on for the next 9E6 to get an accurate median.
In real problems, if you have that much data, you would more likely start to question the iid assumption anyway, and you'd start looking for drifts in the medians within sliding windows. Real problems being real problems, you'd probably find some drift, and this would point out the unhelpfulness of an "all-data" median. ("Since the data is drifting, what is this the median of?")