Dinner-Diner Matching Probabilities

Consider a banquet at which n different entrees are served and k guests have requested each entree. Suppose the dinners are served randomly to the diners. What is the distribution of the number of matches of dinners to the diners who ordered them?

The following graphs illustrate the relationship between the dinner-diner matching probabilities and the normal distribution, and the relationship between the dinner-diner matching probabilities and the Poisson distribution. Sequence numbers refer to sequences listed in N. J. A. Sloane (2001), The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/~njas/sequences/. The integer sequences are the numerators of the discrete probability distributions, laid out in triangular arrays.

This site uses Flash 5.0 to display information. By using Flash 5, the reader can control what information is displayed interactively. If you do not have the Flash 5 player plugin, you may download it here.  If you can not run Flash 5 on your machine, or do not wish to download it, click here to see an animated gif version of the same information.

Each of the graphs that follow shows the exact dinner-diner probabilities as yellow bars. The normal distribution with the same mean and variance is shown as a blue curve, and the Poisson distribution with the same mean is shown as red balls. The graphs are shown in Flash 5 format. Each frame of the Flash 5 movie represents the probability distribution of the number of matches for n suits and k cards of each suit (n entrees and k diners who have ordered each entree). Each graph also corresponds to a row of the triangular array of integers given in The On-Line Encyclopedia of Integer Sequences in the referenced sequence.  For some of the graphs each row represents an increase by one from the previous row in the number of guests who have ordered each entree, that is, n is constant, but k increases. For other graphs each new frame is an increase of one in the number of entrees available over the previous frame, that is, k is constant, but n increases. The Flash graphs are labeled in terms of card-matching probabilities.  Think of the number of suits of cards as being the number of entrees, and the number of cards of each suit as being the number of guests who have ordered each entree.

The first movie shows how the probability distribution changes when the number of entrees (or suits) is changed and the number of diners (cards of each suit) is fixed. The reader can increase the number of suits by moving the blue slider ball and the number of cards of each suit can be changed by pressing one of the blue buttons. The active choice is backlit with green. The reader may select 2, 3 or 4 suits. The number of cards of each suit is controlled by the slider.  The title of the graph changes as the graphs change.

 

 

The following sequences in The On-Line Encyclopedia of Integer Sequences are related to the probability distributions graphed above. Maple code for generating the sequences is also given in this reference.
Sequence   A059056
(2n)!/2!n
,     Sequence  A059057
(2n)!

Sequence   A059058
(3n)!/3!n
,     Sequence  A059059
(3n)!
Sequence   A059060
(4n)!/4!n
,     Sequence  A059061
(4n)!

Notice that the red balls are centered at the top of the yellow bars when n is quite small. This shows that the exact distribution is well approximated by the Poisson even for fairly small values of n. In the graph, n runs from 1 to 50 when k=2, and from 1 to 25 when k=4. The graph barely changes at all for larger values of n.

Compare the preceding graphs to the one below where the number of entrees is fixed at n=2, n=3 or n=4, but the number of guests increases.

 

 

Sequence   A059064
(2k)!/k!2
,     Sequence  A059065
(2k)!
Sequence   A059066
(3k)!/k!3
,     Sequence  A059067
(3k)!
Sequence   A059068
(4k)!/k!4
,     Sequence  A059069
(4k)!

 

If we had bars of width two at half the height, the blue curve would match perfectly when there are two suits. The reason that the bars have spaces between them when there are two suits is that an odd number of matches of dinners to diners is impossible. Note that the Poisson approximation does not match nearly as well. This is because the variance of the exact distribution is s 2=k2/(2k-1) which is strictly less than the mean for k greater than 1. A Poisson distribution has equal mean and variance. Looking at the graph one can see that the Poisson distribution is overdispersed relative to the exact distribution. For 3 and 4 suits, the normal also serves as a better approximation than the Poisson.