Slide 1Random-Variate GenerationInverse TransformationEmpirical Inverse TransformationEmpirical Inverse TransformationInverse Transformation ExampleRejectionRejection ExampleComposition (Decomposition)Composition ExampleConvolutionChoosing Random-Variate Generation TechniquesWhite SlideRandom-Variate GenerationAndy WangCIS 5930-03Computer SystemsPerformance AnalysisRandom-Variate Generation•Methods to generate nonuniform variables–Each method is applicable to a subset of the distribution–For a distribution, one method may be more efficient than the others23Inverse Transformation•Observation•u = CDF F(x) is uniformly distributed between 0 and 1•x can be generated via F-1(u)•A powerful technique•If F(x) and F-1(x) can be computed0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 200.20.40.60.81CDFxF(x)Empirical Inverse Transformation•Network packet sizes, f(x) = 64 bytes, 70%128 bytes,10%512 bytes, 20%40 64 128 192 256 320 384 448 512 57600.20.40.60.81PMFpacket size (bytes)f(x)CDF F(x) =0.0, 0 < x < 640.7, 64 < x < 1280.8, 128 < x < 5121.0, 512 < x0 64 128 192 256 320 384 448 512 57600.10.20.30.40.50.60.70.80.91CDFpacket size (bytes)F(x)Empirical Inverse Transformation•F-1(u) = 64, 0 < u < 0.7128, 0.7 < u < 0.8512, 0.8 < u < 15Inverse Transformation Example•Exponential distribution•f(x) = e-x•CDF F(x) = 1 - e-x = u•Inverse transformation•x = - ln(1-u)/ •Given that u = U(0,1)•x = - ln(u)/ 60 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 200.20.40.60.811.2PDFxf(x)0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 200.20.40.60.81CDFxF(x)7Rejection•Useful if a PDF g(x) exists so that cg(x) envelopes PDF f(x), where c is a constant•Steps1. Generate x with PDF g(x)2. Generate y uniform on [0, cg(x)]3. If y < f(x), return x, else go to step 1Rejection Example•f(x) = 20x(1 - x)30 < x < 1•Let g(x) = U(0,1)c = 2.058•Steps1. Generate x on [0, 1] according to U(0,1)2. Generate y uniform on [0, 2.058]3. If y < 20x(1 – x)3 return xelse go to step 180 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 100.511.522.5f(x)2.058*U(0,1)xacceptreject9Composition (Decomposition)•Can be used –If CDF F(x) is a weighted sum of CDFs–Or, if PDF f(x) is a weighted sum of PDFs•Steps–Generate u1 ~ U(0,1), u2 ~ U(0,1)–Use u1 to choose fi(x) or Fi(x), return F-1(u2) niiiniiixfpxfxFpxF11,Composition Example•Laplace distribution•a = 2, x > 0 with 50% probability•Steps1. Generate u1 ~ U(0,1)u2 ~ U(0,1)2. If u1 < 0.5return x = -aln(u2)elsereturn x = aln(u2)10axeaxf/21)(-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.500.050.10.150.20.250.3xf(x)11Convolution•Random variable x = y1 + y2 + … yn•x can be generated by summing n random variate yis•Exampley1 = outcome of die 1 (uniform distribution)y2 = outcome of die 2 (uniform distribution)x = sum of outcomes of two dice= y1 + y2 (triangular distribution)Choosing Random-Variate Generation Techniques•Use inversion if CDF is invertible•Use composition if CDF/PDF sum of other CDFs/PDFs•Use convolution if the variate a sum of other variates•Use rejection if a bounding PDF function exists•Use empirical inversion as needed 1213White
View Full Document