Yeah, this is more Martingale territory than clt. I wrote a proof below that gives a limited Martingale property of the process, but I don't know enough further theory to continue. (slash I'm lazy and have better things to do)
Re:Find running median from a stream of integers
by sesqu on Tuesday May 22, 2012 @12:25AM
(#4006262)
It's worth stressing that while the c.l.t. gives a reasonable justification to using that algorithm for the mean, that justification does not extend to the median, which can diverge from the mean by as much as range/2. You'd need to be able to assume something like a connected set.
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.]