Random High-Low Searching

 

Consider a row of n identical boxes arranged in a line from left to right.  We know that in one of the boxes, selected secretly at random, has been placed a red marble, whereas in all the boxes to the left of that box has been placed a black marble, and in all the boxes to the right has been placed a white marble.  Assuming we adopt the strategy of randomly selecting from among the boxes that have not yet been ruled out, what is the expected number of boxes we would need to check to find the red marble?

 

Let fn denote the expected number of guesses before finding the box with the red marble.  Obviously the probability of selecting the correct box on the first guess is 1/n.  If the correct box is not selected on the first guess then the expected number of additional guesses to reach the drawn number is fk, where k is the remaining number of possible choices after the first guess.  Therefore, letting Fk denote the weighted average of fk for all possible k following the first guess, we have

 

 

To determine Fk, suppose the first guess is the jth box. If j is not the correct box then either j is too high and k = j - 1, or else j is too low and k = n - j.  The probabilities of these two outcomes are (j-1)/(n-1) and (n-j)/(n-1) respectively.  Thus the weighted average of all possible values of fk is

 

 

Inserting this expression for Fk into (1) gives the recurrence

 

 

from which it follows that

 

 

In terms of the variable  uj = j fj - 1 this recurrence reduces to

 

 

with u1 = 0.  The solution of this first order recurrence is just

 

 

Expressing this in terms of fn gives the result

 

 

For large n this can be approximated by fn  ≈  2 ln(n) - (3 - 2g) where g = 0.57721... is Euler's constant.

 

By the way, if, instead of choosing randomly from the boxes not already ruled out, we select the box in the middle of the viable range, then the expected number of guesses would be

 

 

where m is the least integer greater than log2(n).  In particular, if n is a power of 2 then

 

 

which approaches ln(n)/ln(2) – 1 for large n. Interestingly, this is just one less than the maximum number of guesses that could be required using the "mid-box" strategy.

 

For a more explicit determination of the constituient probabilities, suppose we are trying to guess a number from 1-10, taking advantage of "high/low" information. Using the optimum binary search, taking the midpoint of the available range on each guess, the expected number of guesses is 29/10.  On the other hand, suppose we randomly pick (from a uniform distribution) any one of the values in the range of possible values. To get a complete picture of how the search progresses we can represent the "nth state" of the search (after n guesses) by 10 numbers p_k(n), k = 1 to 10, representing the probabilities that the remaining search range is exactly k numbers.  We can combine these 10 probabilities into a column vector

 

 

where the superscript T signifies the transpose (to convet from a row vector to a column vector).  Obviously the initial state vector is

 

 

because after 0 guesses the remaining search range is 10 with probability 1.

 

Now we need the transition matrix A that encodes the effect of progressing from one state to the next, i.e., the 10 x 10 matrix A such that  Vn+1 = AVn  for all n.  The component Ai,j represents the probability that the remaining range after n+1 guesses will be i given that the remaining range after n guesses was j.  From this it's clear that Ai,j = 0 for all i,j such that i ≥ j (because we always reduce the remaining range by at least 1 with each guess). Thus, the only non-zero elements of A are above the diagonal.

 

To determine the non-zero components of A, let's first consider a specific example.  If the current search range consists of 7 numbers (labelled 1 through 7 for convenience), what is the probability that after a random guess (and being told whether the target number is above or below this guess) the remaining search range will consist of exactly 4 numbers?  Clearly there are only two ways this can happen: either {our random guess is 3 and the target is one of 4,5,6,7}, or {our random guess is 5 and the target is one of 1,2,3,4}.  In either case we need our random guess to be a specific one of the 7 available numbers and we need the random target to be one of 4 specific numbers.  Thus the probability of one or the other of these happenning is 2[(1/7)(4/7)] = (2)(4)/72, so this is the value of A[4,7].  The same argument works in the general case, so we have

 

 

for all i,j such that i < j.  (For all other i,j we have Ai,j = 0.)

 

By the way, in cases like A3,7 our random guess has only one "viable" outcome (namely, the center number, 4) rather than two, so it might seem that the probability of this transition should be just i/j2 instead of 2i/j2.  However, notice that in these "central" cases we have twice as many viable choices for the target.  In other words, instead of being 2[(1/7)(3/7)] the probability is actually [(1/7)((2)3/7)], so again it equals 2i/j2.

 

We now have our initial state vector V0 and our transition matrix A, so we can explicitly compute the nth state vector by Vn = An V0. These state vectors are as listed below

 

 

 

 

 

 

 

 

 

 

 

At each stage, the complement of the sum of these state probabilities is the probability that the target number has been guessed.  Therefore the probabilities Pr{k} of the target number being guessed on the kth try for k = 1, 2, .., 10 are as listed below

 

 

The expected number of guesses is just the sum of k Pr{k} for k = 1, 2, ..., 10, which gives the result  43391/12600  =  3.4437301..., in agreement with equation (2) for n = 10.

 

Return to MathPages Main Menu