What's the Probability of a drunk man open a door with $n$ possible keys?

Question

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!!

Answer 1

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}.$$

Answer 2

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$$