0

A person has $n$ keys and one lock. After every failed attempt to unlock, the person may pick a new key and discard the old one. What is the expected number of attempts needed to open the lock?

CommonerG
  • 3,273
Suraj Menon
  • 101
  • Welcome to MSE, it will be pretty good if you post what you've tried to get better answers. Have a nice day. – Inceptio May 06 '13 at 16:21
  • 'after every attempt the key replaced it' - what does this mean? – Alex May 06 '13 at 16:22
  • 1
    what is the probability that it takes $k$ tries, for $1 \le k \le n$? – cats May 06 '13 at 16:29
  • This question has been edited very significantly. Suraj, please confirm that it now means what you intended it to mean -- my own interpretation of your original formulation would have been a different one. – joriki May 06 '13 at 16:43
  • A similar question answered here- https://math.stackexchange.com/questions/246855/probability-problem-with-n-keys – Ankit Seth Oct 02 '18 at 13:16

3 Answers3

1

The experiment is equivalent to arranging the $n$ keys in order and trying them one by one till the lock opens. Assuming that all $n!$ orderings are equally likely, the right key is equally likely to be in any of the $n$ positions, that is, $$P\{\text{lock opens on}~i\text{-th try}\} = \frac{1}{n}, ~ i = 1,2,\ldots, n$$ and the average number of tries is $$\frac{1+2+\cdots + n}{n} = \frac{n(n+1)/2}{n} = \frac{n+1}{2}.$$

Dilip Sarwate
  • 25,197
0

The probability of succeeding at the first try is obviously $\frac{1}{n}$. If that fails, there are only $n-1$ keys left so the probability of suceeding at the second try is $\frac{1}{n-1}$. This goes on until the $n$-th trial, at which point there's only one key left, and the probability of success is $\frac{1}{1}$.

Note that the probability of success at the $k$-th trial above is the conditional probability under the assumption that all previous trails failed. So to get the unconditional probability of success at the $k$-th trial, you have to multiply with the probability that the first $(k-1)$ trials failed.

Once you have worked out the probabilities of succeeding exactly at the $k$-th trial, you can compute the expected values of $k$, i.e. the average of all $k$s weighted by their respective probability.

fgp
  • 21,050
0

It is marginally neater to first find the expectation of $Y$, the number of unsuccessful trials. Then our desired expectation is $E(Y)+1$.

Define the random variables $X_1,X_2,\dots,X_{n-1}$ by $X_i=1$ if all trials up to the $i$-th are unsuccessful, and $X_i=0$ otherwise. Then the number $Y$ of unsuccessful trials is $X_1+X_2+\cdots+X_{n-1}$.

By the linearity of expectation, we have $E(Y)=E(X_1)+E(X_2)+\cdots+E(X_{n-1})$.

The probability that $X_i=1$ is $\frac{n-i}{n}$. Add up, $i=1$ to $n-1$. On top, we have (backwards) the sum of the integers from $1$ to $n-1$. So the expectation of $Y$ is $\frac{n(n-1)}{2}\cdot \frac{1}{n}=\frac{n-1}{2}$.

It follows that the expected number of trials is $\frac{n+1}{2}$.

André Nicolas
  • 507,029