Solution Found!
A prize is randomly placed in one of ten boxes, numbered
Chapter , Problem 19(choose chapter or problem)
A prize is randomly placed in one of ten boxes, numbered from 1 to 10. You search for the prize by asking yes-no questions. Find the expected number of questions until you are sure about the location of the prize, under each of the following strategies. (a) An enumeration strategy: you ask questions of the form "is it in box k?" . (b) A bisection strategy: you eliminate as close to half of the remaining boxes as possible by asking questions of the form "is it in a box numbered less than or equal to k?" . Solution. We will find the expected gain for each strategy, by computing the expected number of questions until we find the prize. (a) With this strategy, the probability 1/10 of finding the location of the prize with i questions, where i = 1, . .. , 10, is 1/10. Therefore, the expected number of questions is 10 1 L i = 1 . 55 = 5.5. i=l (b) It can be checked that for 4 of the 10 possible box numbers, exactly 4 questions will be needed, whereas for 6 of the 10 numbers, 3 questions will be needed. Therefore, with this strategy, the expected number of questions is 4 6 - . 4 + - . 3 = 3.4. 10 10
Questions & Answers
QUESTION:
A prize is randomly placed in one of ten boxes, numbered from 1 to 10. You search for the prize by asking yes-no questions. Find the expected number of questions until you are sure about the location of the prize, under each of the following strategies. (a) An enumeration strategy: you ask questions of the form "is it in box k?" . (b) A bisection strategy: you eliminate as close to half of the remaining boxes as possible by asking questions of the form "is it in a box numbered less than or equal to k?" . Solution. We will find the expected gain for each strategy, by computing the expected number of questions until we find the prize. (a) With this strategy, the probability 1/10 of finding the location of the prize with i questions, where i = 1, . .. , 10, is 1/10. Therefore, the expected number of questions is 10 1 L i = 1 . 55 = 5.5. i=l (b) It can be checked that for 4 of the 10 possible box numbers, exactly 4 questions will be needed, whereas for 6 of the 10 numbers, 3 questions will be needed. Therefore, with this strategy, the expected number of questions is 4 6 - . 4 + - . 3 = 3.4. 10 10
ANSWER:Step 1 of 3
We will find the expected gain for each strategy, by computing the expected number of questions until we find the prize.