3
$\begingroup$

I have this following problem in my problem set and I would like to check if my work is in the right directio.

A drunk man with $n$ keys wants to open his door and tries the keys at random. Exactly one key will open the door. Find the mean number of trials if

a) unsuccessful keys are not eliminated from further selections;

b) unsuccsesful keys are eliminated

It seems clear to me that in the first case we have a Geometric distribution with parameter $1/n$, so the expected number of trials is just $n$.

For the second case, my reasoning follows. Let $X$ denote the number of trials until he opens the door.

$P(X = 1) = 1/n$

$P(X = 2) =(n-1)/n \cdot 1/n-1 = 1/n$

$P(X = 3) = (n-1)/n \cdot (n-2)/(n-1) \cdot 1/(n-2) = 1/n$, and so on.

I'm inclined to say that, in the second case, the probabilities over the possible $n$ values of $X$ are uniformly distributed. If this is case, then the average number of trails should be $(n+1)/2$.

Does it seem correct? If not, how to do it? Thanks in advance!!

$\endgroup$
  • 1
    $\begingroup$ Your results are correct. But some calculations for the expected values would be more convincing. $\endgroup$ – callculus Apr 30 '18 at 17:11
  • $\begingroup$ Sure, I agree. This was just to check if my reasoning was on the right path, thanks a lot! $\endgroup$ – Raul Guarini Apr 30 '18 at 17:17
  • $\begingroup$ You´re welcome. $\endgroup$ – callculus Apr 30 '18 at 18:00
1
$\begingroup$

Yes, you are correct. Let $X$ be the number of trials. Expectation value $E[X]$ is given by the standard formula: $$E[X] = \sum\limits_{k=1}^{\infty} k \cdot P(X=k),$$ where $P(X=k)$ is the probability that in the $k$-th trial the guy opened the door.

In the first case, we are returning the key back. If $k$-th trial was successful, then previous $k-1$ should not be. We can write: $$P(X=k) = \left(\frac{n-1}{n} \right)^{k-1}\frac{1}{n},$$ and the expectation value is $$E[X] = \frac{1}{n}\sum\limits_{k=1}^{\infty} k \left(\frac{n-1}{n} \right)^{k-1} = \frac{1}{n} \frac{1}{[1 - (n-1)/n]^2} = n.$$

In the second case, wrong keys are thrown away. The probability in this case is equal to $$ \begin{align} P(X=1) & = \frac{1}{n}, \\ P(X=2) & = \frac{n-1}{n} \cdot \frac{1}{n-1} = \frac{1}{n}, \\ P(X=3) & = \frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{1}{n-2} = \frac{1}{n}, \\ P(X=k) & = \frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \ldots \cdot \frac{n-(k-1)}{n-(k-2)} \cdot \frac{1}{n-(k-1)} = \frac{1}{n}, \\ P(X \geqslant n+1) & = 0. \end{align} $$ The probability that the guy successfully opens the door after any number of trials is the same. Expectation value equals: $$E[X] = \frac{1}{n}\sum\limits_{k=1}^{n}k = \frac{1}{n} \frac{1+n}{2}n = \frac{1+n}{2}.$$

$\endgroup$
1
$\begingroup$

For the first case, let's assume it take $t$ trials. Then we have:

$$t = \frac{1}{n}\cdot 1 + \frac{n-1}{n} \cdot (1 + t)$$

Because there's an $\frac{1}{n}$ chance it only takes $1$ trial and $\frac{n-1}{n}$ chance we didn't make progress at all and still require $t$ trials. Simply solve for $t$.

For the second case, let's assume it takes $t_n$ trials. Then we have:

$$t_1 = 1 \quad \wedge \quad t_n = \frac{1}{n}\cdot 1 + \frac{n-1}{n} \cdot (1 + t_{n-1})$$ $$t_n = \frac{n - 1}{n}t_{n-1} + 1$$

Now you conjectured that $t_n = (n+1) / 2$, by induction $t_1$ holds and we have:

$$t_n = (n+1)/2$$ $$t_{n+1} = \frac{n}{n+1}\cdot (n+1)/2 + 1$$ $$t_{n+1} = (n + 2)/2$$

$\endgroup$
  • $\begingroup$ This is a nice solution, thanks! $\endgroup$ – Raul Guarini Apr 30 '18 at 18:28
  • $\begingroup$ @orlp Something is not right. From the first equation I get $t=1$. $\endgroup$ – WoofDoggy Apr 30 '18 at 19:44
  • $\begingroup$ @WoofDoggy Fixed, $t$ should be $1 + t$. $\endgroup$ – orlp Apr 30 '18 at 20:13

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.