Short note: Convolution in random number

Convolution is a method of generating a random variate that is itself the sum of two or more independent random variables. If Y = X1 + X2 + ... + Xk, where the Xi are independent, then a value of Y is obtained by generating one value of each Xi (from random numbers) and adding them. The distribution of Y is the convolution of the distributions of the Xi.

Examples

• Erlang-k distribution: the sum of k independent exponential variables with mean 1/(kθ). Generate Xi = −(1/kθ) ln Ri, then Y = Σ Xi = −(1/kθ) ln(R1R2...Rk).
• Binomial(n, p): the sum of n independent Bernoulli trials. For each trial, generate R; if R ≤ p count 1, else 0. Then add.
• Normal variate: by the central limit theorem, the sum of 12 uniform random numbers minus 6 is approximately N(0, 1): Z = R1 + R2 + ... + R12 − 6. Then X = μ + σZ.
• Poisson / gamma variates can similarly be built from sums of exponential variables.

Advantages: simple to understand and program, and applies when the inverse transform of the sum is hard to find. Disadvantage: needs k random numbers for each variate, so it is slow when k is large.