Generating Continuous Random VariatesDiscrete-Event Simulation:A First CourseSection 7.2: Generating Continuous Random VariatesSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesSection 7.2: Generating Continuous Random VariatesThe inverse distribution function (idf) of X is the functionF−1: (0, 1) → X for all u ∈ (0, 1) asF−1(u) = xwhere x ∈ X is the unique possible value for F (x) = uThere is a one-to-one correspondence between possible valuesx ∈ X and cdf values u = F (x) ∈ (0, 1)Assumes the cdf is strictly monotone increasingTrue if f (x) > 0 for all x ∈ XSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesContinuous Random Variable idfsUnlike the a discrete random variable, the idf for a continuousrandom variable is a true inversex0.0u1.0F (·)••F−1(u) = x..................................................................................................................................................................................................................................................................Can sometimes determine the idf in “closed form” by solvingF (x) = u for xSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesExamplesIf X is Uniform(a, b), F (x) = (x −a)/(b − a) for a < x < bx = F−1(u) = a + (b − a)u 0 < u < 1If X is Exponential(µ), F (x) = 1 − exp(−x/µ) for x > 0x = F−1(u) = −µ ln(1 − u) 0 < u < 1If X is a continuous variable with possible value 0 < x < band pdf f (x) = 2x/b2, the cdf is F (x) = (x/b)2x = F−1(u) = b√u 0 < u < 1Section 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesRandom Variate Generation By InversionX is a continuous random variable with idf F−1(·)Continuous random variable U is Uniform(0, 1)Z is the continuous random variable defined by Z = F−1(U)Theorem (7.2.1)Z and X are identically distributedAlgorithm 7.2.1If X is a continuous random variable with idf F−1(·), a continuousrandom variate x can be generated asu = Random();return F−1(u);Section 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesInversion ExamplesExample 7.2.4: Generating a Uniform(a, b) Random Variateu = Random();return a + (b - a) * u;Example 7.2.5: Generating an Exponential(µ) Random Variateu = Random();return −µ * log(1 - u);Note: return −µ * log(1 - u) is prefered to return −µ *log(u), though both generate an Exponential random variateSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesExamples 7.2.4 and 7.2.5Algorithms in Example 7.2.4 and 7.2.5 are idealBoth are portable, exact, robust, efficient, clear, synchronizedand monotoneIt is not always possible to solve for a continuous randomvariable idf explicitly by algebraic techniquesTwo other options may be availableUse a function that accurately approximates F−1(·)Determine the idf by solving u = F(x) numericallySection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesApproximate InversionIf Z is a Normal(0, 1), the cdf is the special function Φ(·)The idf Φ−1(·) cannot be evaluated in closed formThe idf can be approximated as the ratio of two fourth degreepolynomials (Odeh and Evans, 1974)The approximation is efficient and essentially has negligibleerrorSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesApproximation of Φ(·)For any u ∈ (0, 1), a Normal(0, 1) idf approximation isΦ−1(u) ≃ Φ−1a(u) whereΦ−1a(u) =(−t + p(t)/q(t) 0.0 < u < 0.5t − p(t)/q(t) 0.5 ≤ u < 1.0andt =(p−2 ln(u) 0.0 < u < 0.5p−2 ln(1 −u) 0.5 ≤ u < 1.0andp(t) = a0+ a1t + ··· + a4t4q(t) = b0+ b1t + ··· + b4t4The ten coefficients can be chosen to produce an absoluteerror less than 10−9for all 0.0 < u < 1.0Section 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesExample 7.2.6Inversion can be used to generate Normal(0, 1) variates:Example: 7.2.6: Generating a Normal(0, 1) Random Variateu = Random();return Φ−1a(u);This algorithm is portable, essentially exact, robust,reasonably efficient, synchronized and monotoneClarity?Section 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesAlternative Method 1If U1, U2, . . . , U12is an iid sequence of Uniform(0, 1),Z = U1+ U2+ . . . + U12− 6is approximately Normal(0, 1)The mean is 0.0 and the standard deviation is 1.0Possible values are −6.0 < z < 6.0Justification is provided by the central limit theorem (Section8.1)This algorithm is: portable, robust, relatively efficient and clearThis algorithm is not: exact, synchronized or monotoneSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesAlternative Method 2If U1and U2are independent Uniform(0, 1) RVs thenZ1=p−2 ln(U1) cos(2πU2)andZ2=p−2 ln(U1) sin(2πU2)will be independent Normal(0, 1) RVs (Box and Muller, 1958)This algorithm is: portable, exact, robust and relativelyefficient;This algorithm is not: clear or monotoneThe algorithm is synchronized only in pair-wise fashionSection 7.2: Generating Continuous Random Variates Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Generating Continuous Random VariatesNormal and Lognormal Random VariatesRandom variates corresponding to Normal(µ, σ) andLognormal(a, b) can be generated by using a Normal(0, 1)random variate generatorExample 7.2.7: Generating a Normal(µ, σ) Random Variatez = Normal(0.0, 1.0);return µ + σ ∗z;/* see Definition 7.1.7 */Example 7.2.8: Generating a Lognormal(a, b) Random Variatez = Normal(0.0, 1.0);return exp(a + b * z);/* see Definition 7.1.8 */Both algorithms are essentially