[Math] Expected value of a guessing game

expectationprobabilityproject euler

I'm trying to solve project euler 527, I don't understand how the expected value of B(6) is taken.

A secret integer t is selected at random within the range 1 ≤ t ≤ n.

The goal is to guess the value of t by making repeated guesses, via
integer g. After a guess is made, there are three possible outcomes,
in which it will be revealed that either g < t, g = t, or g > t. Then
the process can repeat as necessary.

Normally, the number of guesses required on average can be minimized
with a binary search: Given a lower bound L and upper bound H
(initialized to L = 1 and H = n), let g = ⌊(L+H)/2⌋ where ⌊⋅⌋ is the
integer floor function. If g = t, the process ends. Otherwise, if g <
t, set L = g+1, but if g > t instead, set H = g−1. After setting the
new bounds, the search process repeats, and ultimately ends once t is
found. Even if t can be deduced without searching, assume that a
search will be required anyway to confirm the value.

Your friend Bob believes that the standard binary search is not that
much better than his randomized variant: Instead of setting g =
⌊(L+H)/2⌋, simply let g be a random integer between L and H,
inclusive. The rest of the algorithm is the same as the standard
binary search. This new search routine will be referred to as a random
binary search.

Given that 1 ≤ t ≤ n for random t, let B(n) be the expected number of
guesses needed to find t using the standard binary search, and let
R(n) be the expected number of guesses needed to find t using the
random binary search. For example, B(6) = 2.33333333 and R(6) =
2.71666667 when rounded to 8 decimal places.

Find R(1010) − B(1010) rounded to 8 decimal places.

Im trying to get the expected value B(6) as follows:

$$B(6) = \frac16 + 2\cdot\frac13 + 3\cdot\frac23 = 2.8333333$$

I got this from an answer on another thread, the probability to get a correct guess at the n-th time is $\frac{2^{n-1}}{6}$.

As for R(6) I don't understand how to get it.

Could someone explain how to get the B(6) and R(6) exactly?

Best Answer

First of all, the expected value for B (6) is not 2.83333 but rather 2.333333 as is stated in an example in the problem. Second of all, it's kind of against the spirit of project euler to just look up the solution, but here are some recursive formulas to help you along (you'll need a better approach for the full scale problem though.

For B (n), let $ i = \left \lfloor {n + 1 \over 2} \right \rfloor $. Then $$ B (n) = 1 + {i - 1 \over n} B (i - 1) + {n - i \over n} B (n - i) $$ This is one guess plus the number of guesses afterwords if the secret number is lower than the guess times the probability of the secret number being less than the guess plus the number of guesses afterwords if the secret number is higher than the guess times the probability of the secret number being higher than the guess.

For R (n), the randomization makes it less simple, but for any choice of the guess i the expected value for secret values below and above is easily defined recursively as the probability of the secret number being in that range times the recursively calculated expected value. We can't really choose i so we sum over all i and multiply by 1/n, the probability of each one being chosen. Then the above and below recursive terms combine and we get $$ R (n) = 1 + {2 \over n^2} \sum_{i = 1}^{n - 1}{i R (i)} $$

You can easily expand these by hand for n = 6 and I think you might see a pattern.

Related Solutions

[Math] Flaw in expected value solving logic (Project Euler 323)

Each time you OR an $y_i$ into $x_{i-1}$, you are OR-ing a $1$ in the $k$-th position with probability $\frac{1}{2}$, and what you are OR-ing into the $32$ bit positions is $32$ independently chosen bits. If $X_k$ denotes the value of $i$ at which the $k$-th bit turns from $0$ to $1$, then $X_k$ is a geometric random variable with parameter $\frac{1}{2}$. Thus, $$P\{X_k \leq m\} = 1 - P\{X_k > m\} = 1 - \frac{1}{2^m}.$$ Also, the $X_k$'s are independent random variables.

The time $N$ at which you arrive at the all-ONEs state is thus the maximum of $32$ independent geometric random variables with parameter $\frac{1}{2}$. Now, $$P\{N > m\} = P\{\text{at least one}~X_k > m\} = 1 - P\{\text{all}~ X_k \leq m\} = 1 - \left(1 - \frac{1}{2^m}\right)^{32}$$ and $$\begin{align*}E[N] &= \sum_{m=0}^{\infty} P\{N > m\} = \sum_{m=0}^{\infty} 1 - \left(1 - \frac{1}{2^m}\right)^{32} \\ &= 1 + \left[1 - \left(\frac{1}{2}\right)^{32}\right] + \left[1 - \left(\frac{3}{4}\right)^{32}\right] + \left[1 - \left(\frac{7}{8}\right)^{32}\right] + \cdots \end{align*}$$ which should work out to be close to $7$.

Probability – Average Number of Guesses to Guess Number Between 1 and 1000?

Let us take the more ideal case of guessing integers between $1$ and $2^{10}-1=1111111111_2$ writing in base $2$ from now on without explicitly writing subscript $2$ each time. Then the algorithm for the guesses will be like this:

The initial guess is $1\overline 0$ where $\overline 0$ means fill up with zeros until we have a ten digit number
Write the $n$-th guess as $g_n=x_n1\overline 0$ where $x_n$ is a binary string of length $(n-1)$
If the game responds by "higher", the next guess is $g_{n+1}=x_n11\overline 0$
If the game responds by "lower", the next guess is $g_{n+1}=x_n01\overline 0$
If the game responds by "correct" we are done after $n$ guesses

So we see that the game terminates whenever there are only zeros remaining right of $x_n1$. Then note that there are $2^{n-1}$ binary strings $x_n$ of length $(n-1)$. So $2^{n-1}$ numbers are guessed after exactly $n$ guesses. So for this setup the expected number of guesses will be, returning to writing in base $10$: $$ \frac{1}{2^{10}-1}\sum_{n=1}^{10}n\cdot 2^{n-1}=\frac{9217}{1023}\approx9.00978 $$ So the average case here is very close to the worst case of $10$ guesses. This could seem odd at first, but odd is also the clue here ... Half of the time it takes $10$ guesses to reveal that the randomly picked number $x$ is in fact odd. The first $9$ guesses fills up with zeros which in base $2$ means "divisible by $2$". One quarter of the time $x$ is divisible by $2^2=4$ forcing the algorithm to make $9$ guesses before succes. And so on.

I wrote the following code in Python:

L=[1,1000]
G={}
for n in range(1,11):
    i=0
    while i<len(L)-1:
        guess = int(0.5*(L[i]+L[i+1]+1))
        if guess not in L:
            L = L[:i+1]+[guess]+L[i+1:]
            i+=1
            G[guess] = n
        i+=1
S=0
for g in G:
    S+=G[g]
print (10+S+10)

which responded with $8987$, so the average for the $1$ to $1000$ case, assuming that we always make the guess of the rounded average of the limits of the interval we know that $x$ belongs to, must be $8.987$ guesses.

Best Answer

Related Solutions

[Math] Flaw in expected value solving logic (Project Euler 323)

Probability – Average Number of Guesses to Guess Number Between 1 and 1000?

Related Question