APL and the Birthday Problem
Vector 8:4, page 20
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 20
One of the rather beautiful probability problems that our students study is the so-called Birthday problem, which is - what is the probability that amongst N people randomly chosen, there are at least two with the same birthday?
To answer this question, as any other probability problem, assumptions have to be made. In this case, the simplest assumption to make is that for all the N people, all possible choices of their birthdays are equally likely. Let’s suppose N equals 5 (although we might anticipate that the answer for N equal to 5 might be rather small).
It turns out to be easier to calculate the complementary probability that no two people have the same birthday. Hence, in line with the assumption made, the required probability will be the ratio of the total number of possible choices of N birthdays with no two being the same, to the total number of choices without restriction. The first of these is 365×364×363×362×361 (arguing that the first person has 365 choices, the second 364 and so on). With no restriction on whether or not the birthdays coincide, the corresponding calculation is 365×365×365×365×365, and hence the required probability is given by:
Although this APL expression is correct, it is worth pausing a moment to consider the order of execution of this statement. Working from right to left, it is clear that only one division is made, which could result in the calculation of a small number whose inaccuracy will be amplified by the subsequent multiplications. A better way to proceed is to consider the calculation as the multiplication of 5 ratios, equivalent to the APL expression:
(The last pair of brackets is of course superfluous.)
Such an expression is somewhat tedious to type in, and (yes you have guessed it) there is a much better way to construct it which illustrates beautifully the superb array operation facilities of APL. The procedure is to construct a two-row matrix with row 1 equal to 365 364 363 362 361 and the second row 365 365 365 365 365. Then the required probability can be calculated in two stages, first by dividing row 1 by row 2, and then secondly multiplying all elements of the resulting vector. Both operations are one of reduction - i.e. use the APL operator /. For the first operation the reduction has to be over the first dimension of the matrix using ÷ hence the required expression is ÷/[1] or ÷⌿. The second reduction is a times reduction - hence use ×/.
So all that is required now is the two row matrix. This is easily created using the iota function:
and so the required probability that, of 5 people, no two have the same birthday, is given by:
Not surprisingly therefore there is only about a 2.7% chance of there being at least two people amongst the five with the same birthday.
Next, we ask the question - how large does N have to be before there is at least a 50% chance of at least two people having the same birthday? Or equivalently, for what value of N (instead of 5) does the above calculation give an answer less than .5?
Before answering this, note that if we require the answer for the next N, equal to 6, all we require is the product with an additional ratio - namely the ratio 360÷365. Thus if we created a rather large matrix say with 50 columns, then the probabilities of no two people having the same birthday for N equal to 1,2,…50 may be calculated by replacing the times reduction ×/ by a times scan ×\ (note that ×\1 2 3 4 returns the vector 1 2 6 24). Hence the probability vector giving simultaneous answers for N equal to 1,2,…50 may be calculated using
PROB←×\÷⌿(366-⍳50),[0.5]365
PROB[⍳25]
1 0.99726 0.9918 0.98364 0.97286 0.95954 0.94376 0.92566
0.90538 0.88305 0.85886 0.83298 0.80559 0.7769 0.7471 0.7164
0.68499 0.65309 0.62088 0.58856 0.55631 0.5243 0.4927
0.46166 0.4313
And so we see the somewhat surprising result that with N as low as 23, there is at least a 50% chance of there being at least two people with the same birthday!
An alternative way of inspecting PROB to find this out is to use the dyadic iota function
(In other words the first occurrence of 1 in the Boolean vector PROB<.5 occurs at the 23rd term.)
Yet another way is to count how many elements are greater than or equal to .5 and add one, i.e.
The advantage of this approach is that it generalises to calculating several similar facts at one and the same time. Suppose that we want to know the values of N for which PROB first drops below the values .75 .5 .25. Then the expression:
does what is required.
Finally, the Birthday problem gives a Mathematics teacher an opportunity to illustrate the use of logarithms and exponentials. Taking logarithms converts multiplication to addition and division to subtraction. Hence an algebraically equivalent expression may be given by:
Comparison of the two results shows that they are virtually identical to fifteen decimal places: