Problem 67

Problem 67: PIN guessing ( $✓$ ) 2002 Paper I

In order to get money from a cash dispenser I have to punch in a Personal Identiﬁcation Number. I have forgotten my PIN, but I do know that it is equally likely to be any one of the integers $1$ , $2$ , …, $n$ . I plan to punch in integers in ascending order until I get the right one. I can do this at the rate of $r$ integers per minute. As soon as I punch in the ﬁrst wrong number, the police will be alerted. The probability that they will arrive within a time $t$ minutes is $1 - e^{- λ t}$ , where $λ$ is a positive constant. If I follow my plan, show that the probability of the police arriving before I get my money is

\sum_{k = 1}^{n} \frac{1 - e^{- λ (k - 1) ∕ r}}{n} .

Simplify the sum.

On past experience, I know that I will be so ﬂustered that I will just punch in possible integers at random, without noticing which I have already tried. Show that the probability of the police arriving before I get my money is

1 - \frac{1}{n - (n - 1) e^{- λ ∕ r}} .

Comments

This was originally about getting money from a cash dispenser using a stolen card, but it was decided that STEP questions should not be immoral. Hence the rather more improbable scenario.

The exponential distribution, here governing the police arrival time, is often used for failure of equipment (light-bulbs, etc). It has the useful property (not used here) that the reliability for a light bulb (here the probability of the police not coming within a certain time period of duration $t$ ) doesn’t depend on which time period you choose; i.e. given that the light bulb has survived to time $T$ , the probability of it surviving until time $T + t$ is independent of $T$ (which doesn’t seem very suitable for light bulbs). This is referred to as the memoryless property.

To simplify the sums, you have to recognise a geometric series where the common ratio of terms is an exponential; not difficult, but easy to miss the ﬁrst time you see it.

Solution to problem 67

The probability that I get the right number on the $k$ th go is $1 ∕ n$ . The time taken to key in $k$ integers³³ is $(k - 1) ∕ r$ . The probability that the police arrive before this is $1 - e^{- λ (k - 1) ∕ r}$ so the total probability that the police arrive before I get my money is

\sum_{k = 1}^{n} \frac{1}{n} \times (1 - e^{- λ (k - 1) ∕ r}) .

We have

\sum_{k = 1}^{n} \frac{1}{n} \times (1 - e^{- λ (k - 1) ∕ r}) = 1 - \sum_{k = 1}^{n} \frac{e^{- λ (k - 1) ∕ r}}{n} = 1 - \frac{1 - e^{- λ n ∕ r}}{n (1 - e^{- λ ∕ r})},

since the last part of the sum is a geometric progression with common ratio $e^{- λ ∕ r}$ .

This time, the probability of getting my money on the $k$ th go is $1 ∕ n$ times the probability of not having punched in the correct integer in the preceding $k - 1$ turns:

P (money on k th go) = \frac{1}{n} \times {(\frac{n - 1}{n})}^{k - 1} .

Thus the probability of the police arriving before I get my money is

\sum_{k = 1}^{\infty} \frac{1}{n} \times {(\frac{n - 1}{n})}^{k - 1} \times (1 - e^{- λ (k - 1) ∕ r}) = \frac{1}{n} \times \frac{1}{1 - (n - 1) ∕ n} - \frac{1}{n} \times \frac{1}{1 - e^{- λ ∕ r} (n - 1) ∕ n},

which is easily seen to be the given answer.

Post-mortem

For each part, you have to calculate the probability of the ﬁrst success occurring on the $k$ th go. You have to remember to multiply the probability of success on this go by the probability of failure on the preceding $k - 1$ goes — a very typical idea in this sort of probability question. After that, the question is really just algebra. STEP questions on this sort of material nearly always involve signiﬁcant algebra or calculus.

Car batteries as well as light bulbs often crop up as examples of objects to which exponential reliability can be applied. Suppose your car battery has a guarantee of three years, and your car is completely destroyed after two years. Your insurance company offers to give you one third of the price of the battery. What do you think they would say to your counterclaim for the full price, based on the fact that, given it had lasted two years, the exponential model says that it would have had an expected further three years life in it?

³³Think of fences and posts: $k$ posts here but only $k - 1$ fences.