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 f_n 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 f_k, where k is the remaining number of possible choices after the first guess.  Therefore, letting F_k denote the weighted average of f_k for all possible k following the first guess, we have

To determine F_k, 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 f_k is

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

from which it follows that

In terms of the variable  u_j = j f_j − 1 this recurrence reduces to

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

Expressing this in terms of f_n gives the result

For large n this can be approximated by f_n  ≈  2 ln(n) − (3 − 2γ) where γ = 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 log₂(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  V_n+1 = AV_n  for all n.  The component A_i,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 A_i,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)/7², 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 A_i,j = 0.)

By the way, in cases like A_3,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/j² instead of 2i/j².  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/j².

We now have our initial state vector V₀ and our transition matrix A, so we can explicitly compute the nth state vector by V_n = Aⁿ V₀. 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