28-1©2006 Raj JainCSE567MWashington University in St. LouisRandom Variate Random Variate GenerationGenerationRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse567-06/28-2©2006 Raj JainCSE567MWashington University in St. LouisOverviewOverview1. Inverse transformation2. Rejection3. Composition4. Convolution5. Characterization28-3©2006 Raj JainCSE567MWashington University in St. LouisRandomRandom--Variate GenerationVariate Generation! General Techniques! Only a few techniques may apply to a particular distribution! Look up the distribution in Chapter 2928-4©2006 Raj JainCSE567MWashington University in St. LouisInverse TransformationInverse Transformation! Used when F-1can be determined either analytically or empirically.00.5u1.0xCDFF(x)28-5©2006 Raj JainCSE567MWashington University in St. LouisProofProof28-6©2006 Raj JainCSE567MWashington University in St. LouisExample 28.1Example 28.1! For exponential variates:! If u is U(0,1), 1-u is also U(0,1)! Thus, exponential variables can be generated by:28-7©2006 Raj JainCSE567MWashington University in St. LouisExample 28.2Example 28.2! The packet sizes (trimodal) probabilities: ! The CDF for this distribution is:28-8©2006 Raj JainCSE567MWashington University in St. LouisExample 28.2 (Cont)Example 28.2 (Cont)! The inverse function is:! Note: CDF is continuous from the right⇒ the value on the right of the discontinuity is used⇒ The inverse function is continuous from the left⇒ u=0.7 ⇒ x=6428-9©2006 Raj JainCSE567MWashington University in St. LouisApplications of the InverseApplications of the Inverse--Transformation Transformation TechniqueTechnique28-10©2006 Raj JainCSE567MWashington University in St. LouisRejectionRejection! Can be used if a pdf g(x) exists such that c g(x) majorizes the pdf f(x) ⇒ c g(x) > f(x) ∀ x! Steps:1. Generate x with pdf g(x).2. Generate y uniform on [0, cg(x)].3. If y < f(x), then output x and return. Otherwise, repeat from step 1.⇒ Continue rejecting the random variates x and y until y > f(x)! Efficiency = how closely c g(x) envelopes f(x)Large area between c g(x) and f(x) ⇒ Large percentage of (x, y) generated in steps 1 and 2 are rejected! If generation of g(x) is complex, this method may not be efficient.28-11©2006 Raj JainCSE567MWashington University in St. LouisExample 28.2Example 28.2! Beta(2,4) density function:! Bounded inside a rectangle of height 2.11⇒ Steps:" Generate x uniform on [0, 1]." Generate y uniform on [0, 2.11]." If y < 20 x(1-x)3, then output x and return. Otherwise repeat from step 1.28-12©2006 Raj JainCSE567MWashington University in St. LouisCompositionComposition! Can be used if CDF F(x) = Weighted sum of n other CDFs.! Here, , and Fi's are distribution functions. ! n CDFs are composed together to form the desired CDFHence, the name of the technique. ! The desired CDF is decomposed into several other CDFs⇒ Also called decomposition.! Can also be used if the pdf f(x) is a weighted sum of n other pdfs:28-13©2006 Raj JainCSE567MWashington University in St. LouisSteps:! Generate a random integer I such that:! This can easily be done using the inverse-transformation method.! Generate x with the ith pdf fi(x) and return.28-14©2006 Raj JainCSE567MWashington University in St. LouisExample 28.4Example 28.4! pdf:! Composition of two exponential pdf's! Generate! If u1<0.5, return; otherwise return x=a ln u2.! Inverse transformation better for Laplace28-15©2006 Raj JainCSE567MWashington University in St. LouisConvolutionConvolution! Sum of n variables:! Generate n random variate yi's and sum! For sums of two variables, pdf of x = convolution of pdfs of y1and y2. Hence the name! Although no convolution in generation! If pdf or CDF = Sum ⇒ Composition! Variable x = Sum ⇒ Convolution28-16©2006 Raj JainCSE567MWashington University in St. LouisConvolution: ExamplesConvolution: Examples! Erlang-k = ∑i=1kExponentiali! Binomial(n, p) = ∑i=1nBernoulli(p)⇒ Generated n U(0,1), return the number of RNs less than p! χ2(ν) = ∑i=1νN(0,1)2! Γ(a, b1)+Γ(a,b2)=Γ(a,b1+b2)⇒ Non-integer value of b = integer + fraction! ∑ι=1nAny = Normal ⇒∑U(0,1) = Normal! ∑ι=1mGeometric = Pascal! ∑ι=12Uniform = Triangular28-17©2006 Raj JainCSE567MWashington University in St. LouisCharacterizationCharacterization! Use special characteristics of distributions ⇒ characterization! Exponential inter-arrival times ⇒ Poisson number of arrivals⇒ Continuously generate exponential variates until their sum exceeds T and return the number of variates generated as the Poisson variate.! The athsmallest number in a sequence of a+b+1 U(0,1) uniform variates has a β(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 χ2(ν) is the same as a gamma variate γ(2,ν/2).! If x1and x2are two gamma variates γ(a,b) and γ(a,c), respectively, the ratio x1/(x1+x2) is a beta variate β(b,c).! If x is a unit normal variate, eμ+σ xis a lognormal(μ, σ) variate.28-18©2006 Raj JainCSE567MWashington University in St. LouisSummarySummaryIs pdf a sumof other pdfs?Use CompositionYesIs CDF a sumof other CDFs?Use compositionYesIs CDFinvertible?Use inversionYes28-19©2006 Raj JainCSE567MWashington University in St. LouisSummary (Cont)Summary (Cont)Doesa majorizing functionexist?Use rejectionYesIs thevariate related to othervariates?Use characterizationYesIs thevariate a sum of othervariatesUse convolutionYesUse empirical inversionNo28-20©2006 Raj JainCSE567MWashington University in St. LouisExercise 28.1Exercise 28.1! A random variate has the following triangular density:! Develop algorithms to generate this variate using each of the following methods:a. Inverse-transformationb. Rejectionc. Compositiond. Convolution28-21©2006 Raj JainCSE567MWashington University in St. LouisHomeworkHomework! A random variate has the following triangular density:! Develop algorithms to generate this variate using each of the following methods:a. Inverse-transformationb. Rejectionc. Compositiond.
View Full Document
Unlocking...