Analysis of a biased random walk related to median finding

Imagine a process with two variables min and max, and two counters hi and lo.

We initialize min and max by selecting two random numbers (assume a uniform (0,1) distribution for convenience), and sorting them. We also set the hi and lo counters to 0.

At each step we select a new random number r from our distribution and do the following

if (r < min) {
lo++;
} else if (r > max) {
hi++;
} else if (lo > hi) {
max = r;
hi++;
} else if (hi > lo) {
min = r;
lo++;
} else {
if (rand(0,1) > 0.5 ){
max = r;
hi++;
} else {
min = r;
lo++;
}
}


If the random number is outside our range, we increment the appropriate counter, and if it lies inside our range we increment the lower counter and adjust our range appropriately. The question is, after n iterations, where do we expect min and max to end up.

It can be seen that the difference between min and max (assuming a uniform(0, 1) distribution) is distributed as the minimum of n + 2 uniform (0, 1) random variables. However, it should be possible to say considerably more about the location of min and max over time.

Edit This algorithm is only vaguely related to median finding. The process given here just takes a sequence of unifomly distributed random numbers and attempts to guess the median by remembering only two values. This, of course is not an effective method, but similar algorithms are used (remembering more than two variables).

The process that I want to analyze has two values and two counters, and takes a sequence of random numbers, if the random number is larger than both, then increase the hi counter, if the number is smaller than both then increase the lo counter, and if the number lies between the two, either replace max with the current number and increase hi or else replace min with the current number and increase lo, whichever makes the hi or lo counters closer (in cases where either choice could be made, flip a coin). hi and lo are counting the numbers that we have seen that are larger than max or smaller that min respectively.

What I want to know, is how to figure out the distribution of min and max as the number of iterations becomes large, also of interest is the distribution of hi - lo. I can find the distribution of max - min using elementary order statistics.

If min = max, then hi - lo is an ordinary one dimensional random walk, and is easy to analyze. When they are different the walk is subtly biased towards 0. Similarly the values of min and max are biased towards 0.5, I want to know how to find out by how much they are biased.

-