The Birthday Problem

Suppose you walk into a room and start asking people for their birthdays. How long do you expect to wait before someone shares a birthday with a person you already asked? Most people give an answer that is much larger than what actually happens. This gap between expectation and reality is the starting point for this article. It also shows one of the most useful properties of arrays, random access, and how a simple array lets a program answer the question quickly.

Keep one question in mind as you read: when a program wants the value at one particular position, how does it get there? The answer depends on whether the access is direct, and the rest of this article explains what that means and why it matters.

Up to this point, the array examples in the course have used sequential access. In sequential access, the elements of an array are processed one after another, in the order they appear. You start at the first position, move to the second, then the third, and so on until you finish. Many useful tasks look like this, such as totaling all the values in a list or scanning for the largest one.

Sequential access describes how the work is ordered, not a limit on what the array can do. When a problem asks you to visit elements in order, sequential processing is the natural fit. The birthday problem does not fit that pattern, and that is where random access becomes important.

Random access means that every element of the array is equally accessible at any given time. Your program does not need to walk through the earlier positions to reach a later one. If you want the element at a particular position, you can go straight to it, whether that position is the first, the middle, or the last.

An array holds a group of values, and each value sits at a numbered position. Positions label the slots, while the values are the contents stored in those slots. The word direct carries the main idea: an array element is identified by its position, so the program can jump straight to the position it needs. Whether that position is first, last, or in the middle makes no difference to how the program reaches it.

This is why arrays are used whenever a program must revisit a specific slot again and again. The source presents this as the defining ability of arrays. Because no slot is closer or more reachable than another, the cost of reaching index 4 is the same as the cost of reaching index 0.

The short Java program below is an original illustration, not the source file. It shows the core move: naming a position in brackets returns the value stored there. The program does not loop through the array to find the value.

Changing the number inside the brackets changes which element is returned, and the program reaches any of them in the same single step. This is the behavior the birthday problem relies on when it looks up a day.

The source uses a five-position diagram, which is a small stand-in for the 365-slot array the birthday problem needs. Each cell can be reached by its index. To check day number 2, the program names used[2] and reads it. It does not need to inspect used[0] or used[1] first. Those two cells hold true and false respectively, but they have no bearing on the lookup of position 2.

To simulate the birthday experiment, the program must remember which birthdays it has already seen. There are 365 possible birthdays, and the setup ignores leap years. For each possible birthday, the program needs one piece of information: has someone with this birthday already been found? The answer is a boolean value. Gathering 365 boolean answers into one structure is exactly what an array is for.

Each slot corresponds to one day number. The value in used[i] is true if someone whose birthday is day number i has already been selected, and false otherwise. The index does the work of identifying the day. The program never searches the array for a matching birthday. It jumps straight to the slot that matches the birthday it just drew.

New boolean arrays start with false in every slot, so unseen birthdays need no setup before they are checked. The same idea explains why the array is initialized with false values: every day is ready to be checked the moment the simulation begins.

Each time the simulation picks a person, the birthday drawn could be any day from 0 to 364. The next birthday has no relationship to the previous one, so the program cannot know in advance which slot it will need. A purely sequential scan would waste effort walking past slots that have nothing to do with the new birthday. Random access solves this: the program computes the day number, reads used at that index, and either stops or records the day as used.