# Simple Probability - Enumeration and Geometric Distributions

I am not sure as to why this particular practice problem does not use a geometric distribution.

A prize is randomly placed in one of ten boxes, numbered from 1 to 10. You search for the prize asking yes-no questions. Find the expected number of questions until you are sure about the location of the prize, under the following strategies.

(a) An enumeration strategy: you ask questions of the form "is it in box k?".

The solution gives the expectation to be: $$\frac{1}{10}\sum_{i=0}^{10}i = 5.5$$

Which is not the expectation for a geometric distribution. Why can't a geometric distribution be applied to this problem? The definition I have been given for a geometric random variable is the number of independent trials until the first "success". Where each trial has a probability of p. What would be the correct way to determine the distribution for this problem?

• The trials are not independent. Presumably we do not make a guess, and after being told no, perhaps make the same guess. It would be geometric if the guesser had "no memory." – André Nicolas May 2 '16 at 21:49
• Yeah I realized after looking it over that its not independent, @GrahamKemp gave a good explanation of how to derive the actual expectation. – Cameron May 2 '16 at 23:50

Which is not the expectation for a geometric distribution. Why can't a geometric distribution be applied to this problem? The definition I have been given for a geometric random variable is the number of independent trials until the first "success". Where each trial has a probability of p. What would be the correct way to determine the distribution for this problem?

Short answer: The $p$ is not constant.

The probability of knowing where the box is on the $k$-th answer can be viewed as the probability of $k-1$ failures of decreasing conditional probability, followed by a success -- except on the nineth question we will know where the item is whether the answer is "yes" (there) or "no" (the last box).

This is somewhat like a geometric distribution, however the success rate is not independent of the trial index, and we definitely will know where the item is within nine question.

\begin{align}\mathsf P(X=k) ~=~ & \overbrace{\frac 9{10}\cdot\frac{8}{9}\cdots\frac{11-k}{12-k}}^{k-1\textsf{ failures}}\cdot\overbrace{\frac1{11-k}}^{\textsf{success}}~\mathbf 1_{k\in\{1,..,8\}} + \overbrace{\frac 9{10}\cdot\frac{8}{9}\cdots\frac{2}{3}}^{8\textsf{ failures}}\cdot\frac{2}{2}~\mathbf 1_{k=9} & \star \\[1ex] ~=~& \dfrac 1{10}\mathbf 1_{k\in\{1,..,8\}}+\dfrac 2{10}\mathbf 1_{k=9}\end{align}

This gives the expectated count of questions asked as: $~\dfrac {18}{10}+\sum\limits_{k=1}^8\dfrac k{10}~$, which is $~5.4~$.

(PS: As others pointed out the original answer of $5.5$ presumes we would ask the tenth question anyway; even though we'd certainly know where the item was before then.)

$^\star~$ Well we could just say the probability of the item being in the $k$-th box is $\tfrac 1{10}$, but that is not as illustrative.

Andre is right about why this is not a geometric distribution. But actually, the expectation given in your solution is also incorrect. The correct answer is the the question posed is 5.4.

The point is that if after guess 9 you have not received any answer of "yes" then you can deduce for sure that the prize is in the remaining unasked-about box.