Unformatted text preview:

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

FSU CIS 5930r - Random Variate Generation

Download Random Variate Generation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Random Variate Generation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Random Variate Generation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?