Previous Table of Contents Next


28.3 COMPOSITION

This technique can be used if the desired CDF F(x) can be expressed as a weighted sum of n other CDFs F1(x), F2(x),..., Fn(x). That is,

Here, pi ≥ 0, and Fi’s are distribution functions. The number of functions n can be finite or infinite. Thus, n CDFs are composed together to form the desired CDF; hence, the name of the technique. Another view of the same process is that the desired CDF is decomposed into several other CDFs. This is why the same technique is also called decomposition.

The technique can also be used if the density function f (x) can be expressed as a weighted sum of n other density functions:

In either case, the steps to generate X are as follows:

1.  Generate a random integer I such that

P(I = i) = pi

This can easily be done using the inverse-transformation method.
2.  Generate x with the ith pdf fi(x) and return.


FIGURE 28.3  Laplace density function.

Example 28.4 The pdf for Laplace distribution is given by

A plot of the pdf with a = 2 is shown in Figure 28.3. The pdf is a composition of two exponential pdf’s. The probability of x being positive is ½. Similarly, the probability of x being negative is ½.

Using the composition technique, Laplace variates can be generated as follows:

1.  Generate u1 ~ U(0, 1) and u2 ~ U(0, 1).
2.  If u1 < 0.5, return x = –a ln u2; otherwise return x = aln u2.

It must be pointed out that Laplace variates can be generated more efficiently using the inverse-transformation technique.

28.4 CONVOLUTION

This technique can be used if the random variable x can be expressed as a sum of n random variables y1, y2,..., yn, that can be easily generated; that is,

x = y1 + y2 + ... + yn

In this case, x can be generated by simply generating n random variate yi’s and then summing them.

If x is a sum of two random variables y1 and y2, then the pdf of x can be obtained analytically by a convolution of the pdf’s of y1 and y2. This is why the technique is called convolution, although no convolution is required in random-number generation.

Notice the difference between composition and convolution. The former technique is used when the pdf or CDF can be expressed as a sum of other pdf’s or CDFs. The latter technique is used when the random variable itself can be expressed as a sum of other random variables.

Some examples of applications of this technique are as follows:

  An Erlang-k variate is the sum of k exponential variates Thus, it can be obtained by generating k exponential variates and summing them.
  A binomial variate with parameters n and p is a sum of n Bernoulli variates with success probability p. Thus, a binomial variate can be obtained by generated n U(O, 1) random numbers and returning the number of random numbers that are less than p.
  The chi-square distribution with v degrees of freedom is a sum of squares of v unit normal N(0, 1) variates.
  The sum of two gamma variates with parameters (a, b1) and (a, b2) is a gamma variate with parameter (a, b1 + b2). Thus, a gamma variate with a noninteger value of b parameter can be obtained by adding two gamma variates—one with integer b and the other with the fractional b.
  The sum of a large number of variates from any distribution has a normal distribution. This fact is used to generate normal variates by adding a suitable number of U(0, 1) variates.
  The sum of m geometric variates is a Pascal variate.
  The sum of two uniform variates has a triangular density.

28.5 CHARACTERIZATION

Special characteristics of some distributions allow their variates to be generated using algorithms specially tailored for them. All such algorithms are classified under the technique of characterization.

Examples of randorn-variate generation using characterization are as follows:

  If the interarrival times are exponentially distributed with mean 1/λ, the number of arrivals n over a given period T has a Poisson distribution with parameter λT. Thus, a Poisson variate can be obtained by continuously generating exponential variates until their sum exceeds T and returning the number of variates generated as the Poisson variate.
  The ath smallest number in a sequence of a + b + 1 U(0, 1) uniform variates has a beta(a, b) distribution.
  The ratio of two unit normal variates is a Cauchy (0, 1) variate.
  A chi-square variate with even degrees of freedom X2(v) is the same as a gamma variate γ(2, v/2).
  If x1 and x2 are two gamma variates γ(a,b) and γ(a,c), respectively, the ratio x1/(x1 + x2) has a beta(b,c) distribution.
  If x is a unit normal variate, eµ + σx is a lognormal (µ, σ) variate.


FIGURE 28.4  Finding a random-variate generation technique

Figure 28.4 presents a flow chart that will help you decide which of the preceding techniques to use for a particular case. If the CDF is easily invertible, inverse transformation is the best choice. Otherwise, if either the CDF or pdf can be expressed as a sum of other CDFs or pdfs, the composition method can be used. If the variate can be expressed as a sum of other variates, use convolution. Characterization can be used if the distribution has some known properties that can be exploited for random-variate generation. Finally, if the pdf is such that a majorizing function can be found, the rejection technique can be used. If all else fails, you can always use empirical inverse transformation by numerically computing the distribution function and using it as illustrated earlier in Example 28.2.

EXERCISE

28.1 A random variate has the following triangular density:

f(x) = min(x, 2 – x) 0 ≤ x ≥ 2

Develop algorithms to generate this variate using each of the following methods:

a.  Inverse transformation
b.  Rejection
c.  Composition
d.  Convolution


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.