The Ball and Cell Model

The Basic Model

The ball and cell model is a basic probability model, like the ball and urn model and the Bernoulli trials process. We have n distinct cells, labeled from 1 to n, and we place distinct balls (labeled 1, 2, ...) randomly into the cells. Each ball is equally likely to go into any of the n cells, independently of the placement of any other ball. When a cell contains one or more balls, we will say that the cell is occupied.

Keep in mind that the terms “ball” and “cell” are generic (just like the terms “success” and “failure” in Bernoulli trials) and can actually mean different things in different contexts. Thus, like other basic models, this one fits a great number of different situations. Here are some examples that will be of particular interested to us:

Sampling with replacement. Suppose that we have a finite population of n objects (which we might as well label from 1 to n). We draw objects from the population at random and with replacement. Thus, each time we draw an object from the population, we note its identity and then return it to the population before the next draw. This sampling procedure is equivalent to the ball and cell model with n cells: getting object j on draw i is equivalent to placing ball i into cell j. The discussion of the ball and urn model contains more information about sampling with and without replacement.
Birthdays. Suppose that we choose people at random and note their birthdays. If we assume that birthdays are uniformly distributed throughout the year (and if we ignore leap years) then we have the ball and cell model with n = 365 cells: person i having birthday j is equivalent to placing ball i into cell j. Similarly, if we note the birth month of the people then we have the ball and cell model with n = 12 cells.
Coupon collecting. Suppose that there are n types of coupons (for example, baseball cards). Each time you purchase a certain product (for example, bubble gum), you receive one of the coupons, which is equally likely to be any of the n types. This process is equivalent to the ball and cell model with n cells: getting a coupon of type j on purchase i is equivalent to placing ball i into cell j.

The Experiments

We will be interested in two experiments for the ball and cell model that are in a sense dual to one another. The first experiment (referred to as the birthday experiment) is to distribute a fixed number of k balls into the cells; the main random variable of interest for this experiment is the number of occupied cells. The second experiment (referred to as the coupon collector experiment) is to distribute balls into the cells until a fixed number j are occupied. The main random variable of interest for this experiment is the number of balls required. The two experiments and their random variables are dual in the sense that the roles of parameter and variable are interchanged: the first experiment is to distribute a fixed number of balls into the cells and count the number occupied cells; the second experiment is to distributed balls until a fixed number of cells are occupied and count the number of balls.