2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

Here's a simple way to understand B(6)

when t=1, then the g progression would be 3 then 1

t=2, g progression 3,1,2

t=3, => 3

t=4, => 3,5,4

t=5, => 3,5

t=6, => 3,5,6

In total there were 14 guesses and there were 6 possible t. 14/6=2.3333333, which is the expected number of guesses.

That of course, is not the way to do B(1000000000)!

Cheers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.