Random HighLow 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 (j1)/(n1) and (nj)/(n1) 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_{1} = 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  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 log_{2}(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 "midbox" strategy. 

For a more explicit determination of the constituient probabilities, suppose we are trying to guess a number from 110, 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 nonzero elements of A are above the diagonal. 

To determine the nonzero 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^{2}, 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^{2} instead of 2i/j^{2}. 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^{2}. 

We now have our initial state vector V_{0} and our transition matrix A, so we can explicitly compute the nth state vector by V_{n} = A^{n} V_{0}. 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. 
