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

-

You can deal with the min and max separately, it is clear that after only for first two observations they do not affect each other at all.

Let us look first at the sequence of minimums only, without worrying about how long it takes them to appear. The first minimum, call it $m_1$, is the first observation, $m_1 = x_1$ and is uniform on $[0,1]$. The second minimum is the first observation to be smaller than $m_1$ and is therefore uniformly distributed on $[0, m_1]$. Similarly, $m_k$ is uniformly distributed on $[0, m_{k-1}]$. This means that $m_k$ is the product of $k$ independent copies of $[0,1]$. You can show this very simply by induction.

Now, we can analyse the product of i.i.d random variables using logs and the usual tools for analysing sums. We get that the expectation of $m_k$ is asymptotically $\frac{1}{e^k}$. Although the average of a uniform distribution on $[0,1]$ is $\frac{1}{2}$, the long-term trend of the product is smaller than $\frac{1}{2^k}$. This is because of the convexity of $\log$: hand-wavingly, if a value is close to $1$ we are only twice as big as the expectation $\frac{1}{2}$, whereas if the value is close to $0$ we could be hundreds or thousands of times smaller than $\frac{1}{2}$ with reasonably large probability.

Now, how long does the $k$th minimum take to appear? Given that the $(k-1)$th minimum $m_{k-1}$ has just appeared, this is is easy - on average it takes $\frac{1}{m_{k-1}}$ trials to find an observation which is smaller than $m_{k-1}$. So to find the expected time of appearance of the $k$th minimum, we can just add $$1 + e + e^2 + \ldots + e^{k-1}$$ This is basically $e^{k-1}$ times a constant, or equivalently $e^k$ times a constant. So the $m_k$ is roughly $\frac{1}{e^k}$ and is roughly the $(e^k)$th observation.

This tells us that the minimum of the first $n$ observation is about $\frac{c}{n}$. We can work out an average for $c$ which is between $\frac{1}{2}$ and $1$, but since the minimum of the first $n$ is also likely to be the minimum of the first $n+1$, $n+2$, ... and so on for quite a long time, the actual values of $c$ vary over quite a large range. Individual values of the sequence are all pretty close to $\frac{1}{n}$, but the sequence is always constant for large contiguous ranges and never 'settles down' to be close 'in shape' to the sequence $\frac{1}{n}$.

We also know that the shape of the distribution of the minimum of $n$ observations, asymtotically. It tends to the exponential distribution. This can be seen by the close connection between the exponential distribution and the Poisson process.

For arbitrary distributions other than the uniform, some of this is unchanged, such as the time taken to find a new minimum.

You should be able to calculate a lot of what you're interested in using the above. Many much more sophisticated questions about the distances between adjacent (in numerical order) observations from the uniform distribution, can be answered using the Laplace transform.

-