5
$\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$
3
  • 1
    $\begingroup$ Your results are correct. But some calculations for the expected values would be more convincing. $\endgroup$ Commented Apr 30, 2018 at 17:11
  • $\begingroup$ Sure, I agree. This was just to check if my reasoning was on the right path, thanks a lot! $\endgroup$ Commented Apr 30, 2018 at 17:17
  • $\begingroup$ You´re welcome. $\endgroup$ Commented Apr 30, 2018 at 18:00

2 Answers 2

4
$\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
  • 1
    $\begingroup$ Wrt the expectation value of the first case: Could you explain, how you got from the left term to the right term (eliminating the summation)? $\endgroup$
    – Murmel
    Commented Nov 20, 2019 at 12:06
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$
2
  • $\begingroup$ @orlp Something is not right. From the first equation I get $t=1$. $\endgroup$
    – WoofDoggy
    Commented Apr 30, 2018 at 19:44
  • $\begingroup$ @WoofDoggy Fixed, $t$ should be $1 + t$. $\endgroup$
    – orlp
    Commented Apr 30, 2018 at 20:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .