Find running median from a stream of integers

Re:Find running median from a stream of integers by bjornsing on Monday May 21, 2012 @06:57PM (#4005326)

> It is easy to prove that...

Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem. :)

But it does sound both plausible and brilliant. How do you prove it (in broad terms)?

[ Parent | on HN ]

Re:Find running median from a stream of integers by tel on Monday May 21, 2012 @08:04PM (#4005576)

I can't think of an easy proof but it is clear that such a sequence of estimators, {V_n}, has the median as a fixed point in the following sense.

Assume V_(n-1) = median(X) for the data stream X_n. Now we have

    E[V_n | V_(n-1)] = V_(n-1) + E[signum(V_(n-1) - X_n)]

but by the definition of the median, the right hand side expectation is 0, so the random process is fixed in expectation.

Proving it'll converge to that value would be harder, though. It'll probably depend on the data being much larger than the step size (which is 1).

[ Parent | on HN ]

Re:Find running median from a stream of integers by njs12345 on Monday May 21, 2012 @08:21PM (#4005632)

Slightly off topic, but looks like toemetoch has tripped one of the hellban filters, isn't a spammer, and has no contact info in his profile. Might want to sort that out if you're reading this toemetoch!

[ Parent | on HN ]

Re:Find running median from a stream of integers by pg on Tuesday May 22, 2012 @02:47AM (#4006576)

No, he just accidentally posted the same comment twice. The new one got autokilled. Then he deleted the first one, leaving a single dead comment.

[ Parent | on HN ]

Re:Find running median from a stream of integers by toemetoch on Tuesday May 22, 2012 @02:51AM (#4006587)

Thanks for the info. Account seems to be normal again, mental state is not.

[ Parent | on HN ]

Re:Find running median from a stream of integers by geebee on Monday May 21, 2012 @07:36PM (#4005470)

as we said in college, "the proof is trivial and is left for the grader"

[ Parent | on HN ]

Re:Find running median from a stream of integers by derleth on Monday May 21, 2012 @08:13PM (#4005608)

toemetoch, who is dead, said:

"In a normal distribution the probability of a value higher or lower than mean is 50%. So if you find mean, the average of your +1/-1 noise is zero -> if you're on mean you'll remain there.

If you're not on mean you have a (50 + error)% chance of moving towards mean and (50 - error)% chance of moving away from mean on the next random value -> the trend is towards mean."

[ Parent | on HN ]

Re:Find running median from a stream of integers by toemetoch on Tuesday May 22, 2012 @02:10AM (#4006470)

toemetoch, who is dead

... I'm not following. I can see my reply a few posts down. I accidentally hit submit twice, deleted one but the second one is still there.

Edit: The same technique can be found in some 1-bit ADCs, I believe it's delta-sigma ADC.

[ Parent | on HN ]

Re:Find running median from a stream of integers by derleth on Tuesday May 22, 2012 @03:30AM (#4006669)

Odd. I still only see one response from you with that content, and it is dead.

[ Parent | on HN ]