Find running median from a stream of integers • Hacker News Board

Re: Find running median from a stream of integers

#11

Post by toemetoch » Mon, May 21, 2012, 11:20 PM UTC

bjornsing wrote: post #8

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

> 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)?

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.

Re: Find running median from a stream of integers

#12

Post by geebee » Mon, May 21, 2012, 11:36 PM UTC

bjornsing wrote: post #8

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

> 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)?

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

Re: Find running median from a stream of integers

#13

Post by tel » Tue, May 22, 2012, 12:04 AM UTC

bjornsing wrote: post #8

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

> 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)?

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).

Re: Find running median from a stream of integers

#14

Post by derleth » Tue, May 22, 2012, 12:13 AM UTC

bjornsing wrote: post #8

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

> 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)?

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."

Re: Find running median from a stream of integers

#15

Post by njs12345 » Tue, May 22, 2012, 12:21 AM UTC

bjornsing wrote: post #8

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

> 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)?

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!

Re: Find running median from a stream of integers

#16

Post by yummyfajitas » Tue, May 22, 2012, 12:50 AM UTC

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem.

I'm not sure what proof you have in mind, but I don't think using the word "converge" is correct.

Near as I can tell, your algorithm is x[n+1]= x[n] + sign(sample[n]-x[n]).

If you are applying the c.l.t. to sign(sample[n]-x[n]), all this says is that your algorithm will output a gaussian random variable with mean=median(samples), but sigma=sqrt(n). But maybe that isn't the proof you were thinking of?

[edit: also, the clt doesn't apply to sign(sample[n]-x[n]), since that isn't an i.i.d. sequence of random variables (it's not identical).

One possible proof I thought of: consider probability vectors of the form p[n] = [P(x[n] = 1), P(x[n] = 2), ...]. You can write the evolution of the probability vectors as matrix problem, p[n+1]=A p[n]. I'll bet you can break A = Projection onto median + remainder and show the remainder has norm less than 1. Just a guess, but I think it might work.]

Re: Find running median from a stream of integers

#17

Post by mturmon » Tue, May 22, 2012, 2:16 AM UTC

notaddicted wrote: post #4

This is kind of a weird problem, because it requires you to keep all the numbers in memory, so the "streaming" aspect is a lot less useful. And then once you have the list in memory there are linear median finding algorithms. The only way out that I can see is if you expect the incoming data to follow a normal distribution you can short-circuit the entire problem and just calculate the mean. EDIT: One could construct…

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?")

Re: Find running median from a stream of integers

#18

Post by mturmon » Tue, May 22, 2012, 2:20 AM UTC

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

OTOH, if you know they're integers (as you assume), you might use a simple histogram. Not the same, because you'd have to range the histogram -- but we seem to not mind throwing out a lot of data to get in the ballpark anyway.

And if you don't know they're integers, you have to find a scaling rule for your increment that assures convergence. This is the same problem as bucket size selection for the histogram.

Re: Find running median from a stream of integers

#19

Post by [deleted] » Tue, May 22, 2012, 3:19 AM UTC

yummyfajitas wrote: post #16

dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. I'm not sure what proof you have in mind, but I don't think using the word "converge" is correct. Near as I can tell, your algorithm is x[n+1]= x[n] + sign(sample[n]-x[n]). If you are applying the c.l.t. to sign(sample[n]-x[n]), all this says is that your algo…

[deleted]

Re: Find running median from a stream of integers

#20

Post by Drbble » Tue, May 22, 2012, 3:21 AM UTC

sixothree wrote: post #2

Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?

Your solution is for median position, not median value, and it would require a queue, not a stack, so unneeded old values could be dropped.