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 (2000), 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.

The preferred version of 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.  To view the site using Flash click here.

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 diamonds. The graphs are shown as animated gif files. Each frame of the gif represents a row of the triangular array. 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.

If two people order each entree, that is, k=2 is fixed, and the number n, of entrees increases, then we have

 

Sequence   A059056
(2n)!/2!n
,     Sequence  A059057
(2n)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, k=2

 

Notice that the red diamonds 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. The gif barely changes at all for larger values of n. The delay for the first two frames is larger (n=1) and (n=2) than for subsequent frames.

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

 

Sequence   A059064
(2k)!/k!2
,     Sequence  A059065
(2k)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, n=2

 

The pink curve represents twice the normal density and can be seen to match the yellow bars exactly. If we had bars of width two at half the height, the blue curve would match perfectly. The two entree dinner-diner probabilities are the discrete analog of the normal distribution. The reason that the bars have spaces between them 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 s2=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.

If three people order each entree, that is, k=3 is fixed, and the number n, of entrees increases, then we have

 

Sequence   A059058
(3n)!/3!n
,     Sequence  A059059
(3n)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, k=3

 

Notice that the red diamonds 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 33. The gif barely changes at all for larger values of n. The delay for the first two frames is larger (n=1) and (n=2) than for subsequent frames.

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

 

Sequence   A059066
(3k)!/k!3
,     Sequence  A059067
(3k)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, n=3

 

Note that the Poisson approximation does not match nearly as well as the normal. This is because the variance of the exact distribution is s 2=2k2/(3k-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.

Below we show the graphs for k=4 diners ordering each dinner, and n=4 different dinners ordered by k diners each. Note that the same pattern holds as above, that is that when the number of diners who have ordered each dinner is fixed, and we let the number of dinners increase, this probability distribution is well approximated by a Poisson distribution with parameter k=4. If we fix the number of dinners, n, and let the number of diners increase, then the dinner-diner matching distribution is well approximated by a normal distribution with mean k and variance s2=k2(n-1)/(nk-1)=3k2/(4k-1).

 

Sequence   A059060
(4n)!/4!n
,     Sequence  A059061
(4n)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, k=4


 

Sequence   A059068
(4k)!/k!4
,     Sequence  A059069
(4k)!

Exact Card-Matching Probabilities

with Normal and Poisson Approximations, n=4

The animated gifs on this page were produced using Maple version 6 with the statistics supplement by Dr. Zaven A. Karian of Denison University and edited using the Gif Construction Set version 2.0a from Alchemy Mindworks.