So a guy attempts to open his front door with his $n$ keys, but of course only one key is right. If he eliminates incorrect keys as he goes, so he never tries a key more than once, find the expected value and the variance of the number of attempts required to open the door.

X: random variable of the number of attempts to open door

$x \in {1,2,3, ... , n}$ and $p(x) = \frac{1}{(n+1)-x}$

  1. Expected Value $$E(X)=\sum_{x=1}^n xp(x)$$ $$=\sum_{x=1}^n x\frac{1}{(n+1-x)}$$

... Wolfram Alpha sum calculator ... https://www.wolframalpha.com/widget/widgetPopup.jsp?p=v&id=29c546473e1c796d6076bb18901b15e7&i0=4133000%20

Question: Where is my mistake?


Ok, so it should be $$=\sum_{x=1}^n x\frac{1}{n}$$ because, if I consider previous the failures of previous attempts, $$=1\frac{1}{n} + 2(\frac{n-1}{n})(\frac{1}{n-1}) + 3(\frac{n-1}{n})(\frac{n-2}{n-1})(\frac{1}{n-2}) ... $$ $$=\frac{1}{n}+2(\frac{1}{n}) + 3(\frac{1}{n}) ... $$ $$=\sum_{x=1}^n x\frac{1}{n}$$ $$=(\frac{1}{n})(\frac{n(n+1)}{2})$$

Is this right?

Therefore, $$E(x) = \frac{n+1}{2} and$$ $$Var(X)=\frac{n^2-1}{12}$$

  • 3
    $\begingroup$ The calculation of probability that he opens the door on try number $x$ must take account of the probability that he failed on tries $1,2,\dots,x-1$ $\endgroup$ – saulspatz Mar 17 at 17:14
  • $\begingroup$ In using wolfram alpha since a sum of positive terms cannot be negative, so there is a glitch somewhere $\endgroup$ – Conrad Mar 17 at 17:30
  • 1
    $\begingroup$ What if he has a spare key on his bunch? That might make trynna better. $\endgroup$ – wolfies Mar 17 at 18:33
  • $\begingroup$ Could be, but the problem says guy is drunk so he may not see well, especially at night; thus, could not find spare key. $\endgroup$ – Angery Doge Mar 18 at 1:33

If the guy randomly sorts the keys and then tries them in the sorted order, the probability that the correct key is at position $x$ is $P(X=x)=\frac{1}{n}$. If you want to calculate the probability using the conditional probabilities for the first $x-1$ attempts to fail, you will of course receive the same result: $$P(X=x) = \cfrac{1}{n+1-x}\prod_{k=1}^{x-1}\cfrac{n-k}{n+1-k} = \cfrac{1}{n+1-x}\cfrac{\prod_{k=1}^{x-1}(n-k)}{\prod_{k=1}^{x-1}(n+1-k)}=\cfrac{\prod_{k=2}^{x}(n+1-k)}{\prod_{k=1}^{x}(n+1-k)} = \cfrac{1}{n}$$ Therefore, $$ E(X) = \sum_{x=1}^{n}x\frac{1}{n} = \frac{n(n+1)}{2}\cdot\frac{1}{n} = \frac{n+1}{2}$$ Maybe this helps?


The probability values $p(x)$ you have calculated are the probabilities that $X$ is at most $x$. The event $X=x$ is not independent of the event $X=y$ for $y< x$.

For any $x\in\{1,\dots,n\}$ we know that $X=x$ if and only if the guy chooses the wrong key for $x-1$ successive times, and then chooses the correct key at the $x$'th try. Now the probability that the first chosen key is correct is $1/{n}$. The second key has probability $1/(n-1)$, and in general $p(x)=\frac{1}{n-x+1}$ as you discovered. Notice though, that these are not the probabilities associated with the event $X=x$. However, we can use these probabilities to find the probability distribution $P$ of $X$. From the characterisation given in the beginning of the paragraph we thus have $$P(x)=\frac{1}{n-x+1}\prod_{i=1}^{x-1}\frac{n-i}{n-i+1}.$$ For $x=1$ we define the empty product to be $1$. With this probability distribution you can apply the usual calculations.


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.