Expected Length of Random Hi/Low Searched

If we are trying to guess a number from 1-10, taking advantage of 
"high/low" information using a binary search, the expected number 
of guesses is 29/10.   But what if, instead of picking our next 
guess as the middle of the remaining range of possible values, 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 you 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 

           V_n = [p_1(n)  p_2(n)  ...  p_10(n)]^T

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

                V_0  =  [0  0  ...  0  1]^T

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, the 10x10 matrix A such
that  V_{n+1} = A V_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 than 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 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
                  A[i,j]  =  2i/j^2      

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

By the way, you might be worried about a case like A[3,7] because in 
such a case our random guess has only one "viable" outcome (namely, 
the center number, 4) rather than two.  Thus we might think 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.

Anyway, 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
  _                                                            _
 |                                                              |
 |    0     0     0     0     0     0     0     0     0     1   |
 |_                                                            _|

  _                                                            _
 |     1     1     3     2     1     3     7     4     9        |
 |    --    --    --    --    --    --    --    --    --    0   |
 |_   50    25    50    25    10    25    50    25    50       _|

  _                                                            _
 |   4609   3349   2509   1879   55   191   119   8             |
 |  -----  -----  -----  -----  ---  ----  ----  ---   0    0   |
 |_ 63000  31500  21000  15750  504  2100  1800  225           _|

  _                                                            _
 |   1571  1063   12287    19    67    4     7                  |
 |  -----  ----  ------   ---   ----  ---   ---    0   0    0   |
 |_ 14000  9000  126000   270   1512  175   900                _|

  _                                                            _
 |   7667   5767   117    97     1     1                        |
 |  -----  -----  ----   ----   ---   ---    0    0    0    0   |
 |_ 81000  81000  2800   4725   126   525                      _|

  _                                                            _
 |   7807    17     5     2      1                              |
 |  ------  ---    ---   ---   ----    0     0    0    0    0   |
 |_ 162000  675    504   675   1890                            _|

  _                                                            _
 |   154     53     13     4                                    |
 |  -----  -----  -----  -----   0     0     0    0    0    0   |
 |_ 10125  10125  10500  23625                                 _|

  _                                                            _
 |    59      2     1                                           |
 |  -----   ----  -----    0     0     0     0    0    0    0   |
 |_ 20250   3375  15750                                        _|

  _                                                            _
 |    22      2                                                 |
 |  -----   -----    0     0    0     0     0     0    0    0   |
 |_ 70875   70875                                              _|

  _                                                            _
 |    1                                                         |
 |  -----     0      0     0    0     0     0     0    0    0   |
 |_ 70875                                                      _|


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{n} of the target number being guessed on the nth 
try for n=1,2,..,10 are as listed below

  1   9  15551   29629   85741   73639    5183    229     23     1
 --  --  -----  ------  ------  -------  ------  -----  -----  -----
 10  50  63000  126000  567000  1134000  283500  70875  70875  70875

The expected number of guesses is just the sum of n*Pr{n} for n=1,2,...,10, 
which gives the result 43391/12600 = 3.4437301...

For a more succinct formula for the expected number of guesses, see
the note Random High-Low Searching.