2
$\begingroup$

Man picks key randomly to try and open his door. If it isn't right one, he tries the next key without returning the first. What is E(X)?

The prior question was what is the average amount of attempts if the keys aren't returned.

This was just simple usage of the expected.value of a geometric distribution, $E(X)=\frac{1}{p}$, where $p=\frac{1}{k}$, so $E(X)=k$.

This question is causing me some trouble.

If he doesn't return the key, the probability to get it on the next attempt is higher (that is, if he fails to get it on the first attempt), and so the probability he'll get it as the number of trials increases, also increases. But it also says the that the probability is uniform across attempts.

I'd appreciate if someone could explain to me how that's possible.

$\endgroup$
  • $\begingroup$ "The prior question" was asked here? Where? If the key is NOT returned, then it's wrong to use the geometric distribution. (Further, I guess $X$ is the number of tries, but it's not defined in the question) $\endgroup$ – leonbloy Aug 2 '16 at 19:05
  • $\begingroup$ If you consider each trial individually the probability is uniform in the sense that each key has the same probability as one another of being the correct key. It is not uniform in the sense that the probabilities are the same as the previous trial. With 10 keys, each key has probability $\frac{1}{10}$. Supposing that the guess was wrong, we move to the next trial with nine keys, each with probability $\frac{1}{9}$ of being right, moving on to the eighth trial with each key probability $\frac{1}{8}$, etc... $\endgroup$ – JMoravitz Aug 2 '16 at 19:06
  • 1
    $\begingroup$ The expected number of attempts when you have $n$ keys (and you don't return them) is the same as asking what the expected value is of rolling an $n$ sided die, which is $\frac{(n+1)}{2}$. You can think of each key as a particular face of a die, and the correct key is the "target" face. $\endgroup$ – user51819 Aug 2 '16 at 19:08
  • 1
    $\begingroup$ This depends on how the key system is designed. If it is a finite state machine, it might not be that it is reset between tries. For example with 4 numbers 1-9 inserted. if the correct key is 1211, then the sequence 111111121113 (just typing numbers from 1111 and onwards) could give a correct hit in just a few strokes- if it keeps in mind only the number of correct consecutive strokes. $\endgroup$ – mathreadler Aug 2 '16 at 19:10
  • 1
    $\begingroup$ Some of us still immediately think of metal objects cut into shapes to engage with a purely mechanical contrivance, when we hear the word "key". $\endgroup$ – Graham Kemp Aug 3 '16 at 3:05
2
$\begingroup$

Arrange the keys randomly in a row from left to right. All arrangements of keys are equally likely.

Since the probabilities are uniform at each trial, reason that the man's chances of success have nothing to do with his strategy for picking keys.

Without loss of generality then, we may assume that the man always picks keys from left to right.

The number of guesses required until the man guesses correctly is then the position of the correct key.    Conclude:

For $k=10$, then: $$\Bbb E[X] = \frac{1}{10}\cdot 1 + \frac{1}{10}\cdot 2 + \dots + \frac{1}{10}\cdot 10 = \frac{1}{10}(1+2+\dots+10)=5.5$$

$\endgroup$
1
$\begingroup$

If he doesn't return the key, the probability to get it on the next attempt is higher (that is, if he fails to get it on the first attempt), and so the probability he'll get it as the number of trials increases, also increases. But it also says the that the probability is uniform across attempts.

I'd appreciate if someone could explain to me how that's possible.

On the first attempt the probability for getting the right key is $1/k$.   If that failed then on the second attempt the (conditional) probability for getting the right key will be $1/(k-1)$.   And so on...  If by chance it he gets down to the last key without prior success, then the probability for it being the right one becomes $1/1$ (well, hopefully, if the right key hasn't been lost).

That is how the conditional probabilities for success on the next try increases with each progressive failure.     IE: the conditional probability for success on trial $x$ when given that none of the prior attempts succeeded is: $$\mathsf P(X=x\mid X>x-1) ~=~ \dfrac 1{k-x+1}\quad\Big[x\in \{1,.., k\}\Big]$$

However, if we were to ask "what is the probability for success on trial $x$," then the probability is not conditioned by prior failures.   Lay out the $k$ keys in a row; ordered by planned order of attempt.  If there is no bias in selecting this order, then we have a discrete uniform distribution; and the probability is $1/k$.   Notice: this is not determined by the position, $x$ (well, if $x$ is in the support).

That is how it is uniform across attempts.     IE: the marginal probability for success on trial $x$ is:$$\mathsf P(X=x) ~=~ \dfrac 1 k\quad\Big[x\in \{1,.., k\}\Big]$$

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