2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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." $\endgroup$ – André Nicolas May 2 '16 at 21:49
  • $\begingroup$ Yeah I realized after looking it over that its not independent, @GrahamKemp gave a good explanation of how to derive the actual expectation. $\endgroup$ – Cameron May 2 '16 at 23:50
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.