Inebriated Unlocking
Paddy returns home after a night of drinking. He safely reaches his front door. Fumbling into his pocket he finds he has ten (seemingly identical) keys. Only one of these is the correct key to his front door. It is dark, and there are no visible distinguishing marks on the keys, nor any way to label them.
Paddy selects one of the keys at random and tries it in the lock. If it is successful, he gets in. If not, he returns the key to his pocket, juggles them around and selects another key at random (it is possible he could select a key he has already tried; possible more than once!). He repeats this process until he eventually gets in.
Question: On average, how many unlock attempts will this technique expect to take him?
Bonus Question: Which unlock attempt is most likely to be successful?
Second Bonus: If, instead of replacing an unsuccessful key back into the same pocket, Paddy discards the bogus key into a different pocket (reducing the number of keys left, and ensuring an incorrect key is not tried more than once), how does this technique reduced the expected number of unlock attempts required to open the door? With this second technique, which unlock attempt is most likely to be successful?
Advertisement:
Selection with replacement
This is Paddy’s first strategy in which he returns an unsuccessful key back into the same pocket.
Let’s define the expected number of unlock attempts to be T.
There is a 1/10 chance that Paddy selects the correct key (taking one attempt), or there is a 9/10 chance that it will have taken him one attempt, been unsuccessful, and so he is back to exactly where he started. We can write this as a self-referential equation
T = 1/10(1) + 9/10(1 + T)
10T = 1 + 9 +9T
T = 10
The expected number of unlock attempts is, therefore, ten attempts.
The expected number of unlock attempts is ten.
As to the bonus question about which unlock attempt is most likely (ignoring the facetious ex-post-facto answer of “the last one he tried!”), seemingly paradoxically, it is his first attempt!
- On his first attempt, he has a 1/10 chance of selecting the correct key.
- To be successful on his second attempt, he must have failed on the first attempt 9/10, and now again has a 1/10 chance of getting the correct key on this second try = 9/10 × 1/10
- To be successful on the third attempt requires failing on the first two attempts (9/10)2 followed by success on the third attempt 1/10 which is (9/10)2 × 1/10
- The longer he keeps going, then less likely it is to be successful on that attempt. On attempt n he is likely to be successful with probability (9/10)n-1 × 1/10
The probabilities get smaller and smaller, but sum up to certainty at the limit. The highest probability is for the first attempt. This is not really a paradox. It's the same basic chance of selecting the correct key, it's just that the longer the 'game is played', the less chance you'll get to be at that stage.
Selection without replacement
This is where Paddy discards each unsuccessful key.
On his first attempt, he has a 1/10 of success.
On his second attempt, he has a 1/9 chance of success (there are now only nine keys), but to get to this point he failed on the first attempt 9/10, so the overall chance is 1/9 × 9/10, and the nine’s cancel to leave a chance of 1/10.
On his third attempt, he must have failed 9/10 × 8/9 and this is multiplied by the 1/8 chance he now has, which cancels out to 1/10 again … and so on.
Each key has a 1/10 probability (which from common sense, and symmetry, seems correct).
Each key attempt has the same chance of success, however, the expected number of unluck attempts is reduced. There is a 1/10 chance of it taking one move, a 1/10 of it taking two moves, 1/10 of it taking three moves …
T = 1/10(1+2+3+4+…+9+10)
T = 5.5
Paddy can reduce the expected number of unlock attempts from 10 to 5.5 by shedding incorrect keys into a different pocket.
With the removal strategy, the worst case is that Paddy will need to try is ten unlock events. With the replacement strategy, theoretically, Paddy could be out there all night!