5
$\begingroup$

You have n keys on your key ring. One of them unlocks the front door, but you don't know which one. Find the expected number of tries it takes to open the front door by using the method of indicator random variables.

Note: We try keys without repeats since that key will never work if it doesn't work once.

My attempt:

Let X be the number of tries we need to open the front door. We see that $$X = 1 + X_1 + X_2 + X_3 + ... + X_n $$ where $X_i = 1$ if the $i^{th}$ try doesn't open the door and $X_i = 0$ if the try opens the door. We need at least one try to open the door which is why there's a $1$ as the first term in the sum.

Using linearity of expectation: $$E[X] = 1 + \sum_i {E[X_i]} = 1 + \sum_i {P(X_i = 1)}$$

Now attempting to find $P(X_i = 1)$. Well we've already tried $i - 1$ keys at this point, so there are $n - i + 1$ keys left. Of those $n - i + 1$ keys, $n - i$ of them are incorrect. Therefore, the probability that the $i^{th}$ try doesn't work is $\frac{n - i}{n - i + 1}$.

So, $$E[X] = 1 + \sum_i {E[X_i]} = 1 + \sum_i {P(X_i = 1)} = 1 + \sum_{i = 1}^{n} \frac{n - i}{n - i + 1}$$ I typed this summation into wolframalpha and got some ugly answer with a $\psi$ in it, while the answer from the book I'm using gives the answer as $\frac{(n+1)}{2}$.

Where am I going wrong? Any advice is appreciated :)

$\endgroup$
  • 1
    $\begingroup$ If we try keys without repeats, then it will take at most $n$ tries to open the door. The book's answer doesn't make sense in this context because $\frac{n(n+1)}2>n$. I may be horribly wrong, or perhaps you're supposed to try keys at random? $\endgroup$ – doobdood Jun 23 '20 at 20:40
  • 2
    $\begingroup$ I don't understand your expression for $X$. In any case, your selection of the order in which to examine the keys amounts to a random permutation of the key and the winning key has an equal chance of appearing anywhere in such a permutation. $\endgroup$ – lulu Jun 23 '20 at 20:41
  • 1
    $\begingroup$ That's the probability on the first try. After that, the probability increases. But that's not important...since it takes you $k$ tries with probability $\frac 1n$ no matter what $k$ is, the answer is $\frac 1n\times \frac {n(n+1)}2=\frac {n+1}2$. $\endgroup$ – lulu Jun 23 '20 at 20:46
  • 1
    $\begingroup$ Your definition of the $X_i$ means that exactly one of the variables $X_i$ is $0$, the rest being $1$, so $X=n$. Your definition of $X$ implies that you actually try every key, continuing to try even after you’ve opened the door. $\endgroup$ – Brian M. Scott Jun 23 '20 at 20:47
  • 1
    $\begingroup$ If you really need to do it via indicator variables, let $Y_i$ be the indicator variable for the event "you test the $i^{th}$ key before you find the right one". Then $E=1+\sum Y_i$ $\endgroup$ – lulu Jun 23 '20 at 20:49
2
$\begingroup$

Here's another way to approach the problem. Since we are attempting the keys without replacement, the probability that the ith attempted key works is:

$$P(\text{1st attempt works}) = \frac{1}{n} $$ $$P(\text{2nd attempt works}) = \frac{n-1}{n} \frac{1}{n-1} = \frac{1}{n}$$ $$P(\text{3rd attempt works}) = \frac{n-1}{n} \frac{n-2}{n-1} \frac{1}{n-2}= \frac{1}{n}$$ $$...$$ $$P(i^{th}\text{ attempt works}) = \frac{1}{n}$$ $$E[X] = (1)\frac{1}{n} + (2)\frac{1}{n} + (3)\frac{1}{n} + (4)\frac{1}{n} + .. + (n)\frac{1}{n} \\ = \frac{1}{n}[1 + 2 + 3 ... + n] \\ = \frac{1}{n}[\frac{n(n+1)}{2}] = \frac{n+1}{2}$$ Where we have used the sum of an arithmetic series to get $[\frac{n(n+1)}{2}]$

$\endgroup$

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.