Enumeration vs Bisection Strategy

[Kakashi]

Homework Statement

A prize is randomly placed in one of ten boxes, numbered 1-10 through with each box equally likely. You search for the prize by asking yes–no questions. Let X denote the number of questions required until you are certain of the prize’s location.

Find the expected value E[X] under each of the following strategies:

(a) Enumeration strategy:
You ask questions of the form “Is the prize in box k?" starting from 𝑘=1 and proceeding sequentially.

(b) Bisection strategy:
At each step, you eliminate as close to half of the remaining boxes as possible by asking questions of the form “Is the prize in a box numbered less than or equal to 𝑘?”

Relevant Equations

E[X]=∑xP(x)

Let tX=Number of questions asked.

Enumeration Strategy:

I ask questions of the form: "Is it in box k?" starting from k=1

Initially each box has probability 1/10. If the answer to "Is it in box 1?" is no, then the prize is uniformly distributed among the remaining 9 boxes and so on. If the prize is in box k then exactly k questions are required. Therefore.

$$ P(X=k)=1/10 , k=1,2,..,10 $$
$$ E[X]=\sum_{k=1}^{10} kP(k)=5.5 $$

Bisection Strategy
To minimize the expected number of questions the first question is "Is it in a box<=5?"

This splits the boxes into {1,2,3,4,5} and {6,7,8,9,10} each with a probability of 1/2.

If the answer is yes, I split {1,2,3,4,5} into {1,2,3} and {4,5} and ask if the prize is in {1,2,3}?

If the answer is no, then the prize is in {4,5}. I split this into {4} and {5} and ask if the prize is in box {4}. In this case the prize is identified in 3 questions.

If the answer is yes, then the prize is in {1,2,3}. I split into {1,2} and {3} and ask if the prize is in {1,2}.

If the answer is no, the prize is in box 3 and is identified in 3 questions.

If the answer is yes I split {1,2} into {1} and {2} and ask if the prize is in box {1}. In this case the prize is identified in 4 questions.

A similar approach applies if the prize is in {6,7,8,9,10}.

If the prize is in {3,4,5,8,9,10} the prize is identified in 3 questions. If the prize is in {1,2,6,7} the prize is identified in 4 questions. Therefore E[X]=6/10*3+4*4/10=3.4

Is this reasoning for the bisection strategy correct? Is there a shorter way to calculate the expected value of X for the bisection stratetgy rather than going through all the possible paths?

 

[haruspex]

Your reasoning is correct and I agree with your answer.
It might shed light on the problem, possibly leading to a smarter method, if you figure it out for all numbers of boxes up to 10. I observe an interesting pattern in how the average number of questions increases as the number of boxes increases.
$p_N/N$, where $p_N$ starts at 0 and increases in the pattern
+2
+3, +3
+4, +4, +4, +4
+5, +5, +5, +5, +5, +5, +5, +5,
….

 

[Filip Larsen]

For the enumeration strategy:

If the prize is in box k then exactly k questions are required.

Indeed, but notice the price is known to be in one of the boxes, so if you have 10 boxes do you then need all 10 questions?

For the bisection strategy:

Is this reasoning for the bisection strategy correct? Is there a shorter way to calculate the expected value of X for the bisection stratetgy rather than going through all the possible paths?

In the given context this looks correct to me.

Bisection on a discrete set of $N = 2^k$ values can be done in exactly $k$ steps, so an overall estimate of how many steps it takes to bisect a set of $N$ values can be found as $k\approx \log_2 N$.