PROBABILITY AND CONVOLUTION

  One way to obtain random integers from a known probability function is to write integers on slips of paper and place them in a hat. Draw one slip at a time. After each drawing, replace the slip in the hat. The probability of drawing the integer i is given by the ratio a_i of the number of slips containing the integer i divided by the total number of slips. Obviously the sum over i of a_i must be unity. Another way to get random integers is to throw one of a pair of dice. Then all a_i equal zero except $a_1 = a_2 = a_3 = a_4 = a_5 = a_6 = {1 \over 6}$.The probability that the integer i will occur on the first drawing and the integer j will occur on the second drawing is a_i a_j. If we draw two slips or throw a pair of dice, then the probability that the sum of i and j equals k is the sum of all the possible ways this can happen:  

$$c_k \eq \sum_i a_i a_{k-i}$$ (57)

Since this equation is a convolution, we may look into the meaning of the Z-transform  

$$A(Z) \eq \cdots a_{-1} Z^{-1} + a_0 + a_1 Z + a_2 Z^2 + \cdots$$ (58)

In terms of Z-transforms, the probability that i plus j equals k is simply the coefficient of Z^k in  

$$C(Z) \eq A(Z)\, A(Z)$$ (59)

The probability density of a sum of random numbers is the convolution of their probability density functions.

EXERCISES:

1. A random-number generator provides random integers 2, 3, and 6 with probabilities p(2)=1/2, p(3)=1/3, and p(6)=1/6. What is the probability that any given integer n is the sum of three of these random numbers? (HINT: Leave the result in the form of coefficients of a complicated polynomial.)