System Modeling and Simulation Recap: Random Number Generation and Variate Techniques
Explore the fundamental concepts of random number generation and variate techniques in system modeling and simulation. Topics include pseudo-random number generation, Bernoulli variates, and the inverse transformation method for discrete distributions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CPSC 531: System Modeling and Simulation Carey Williamson Department of Computer Science University of Calgary Fall 2017
Recap and Terminology (Pseudo-) Random Number Generation (RNG) Random Variate Generation (RVG) A fundamental primitive required for simulations Goal: Uniform(0,1) Uniformity Independence Computational efficiency Long period Multiple streams Common approach: LCG Careful design and seeding Never generates 0.0 or 1.0 Covered in guest lecture (JH) Readings: 2.1, 2.2 Builds upon Uniform(0,1) Goal: any distribution Discrete distributions Continuous distributions Independence (usually) Correlation (if desired) Computational efficiency Common approach: the inverse transform method Straightforward math (usually) Might generate 0.0 or 1.0 Covered in today s lecture Readings: 6.1, 6.2 2
Outline Random variate generation Inverse transform method Convolution method Empirical distribution Other techniques 3
Discrete-Event Simulation Input parameters such as inter-arrival times and service times are often modeled by random variables with some given distributions A mechanism is needed to generate variates for a wide class of distributions This can be done using a sequence of random numbers that are independent of each other and are uniformly distributed between 0 and 1 4
Uniform Random Numbers Uniformly distributed between 0 and 1 Consider a sequence of random numbers u1,u2, ,uN n equal sub-intervals 0 1 Uniformity: expected number of random numbers in each sub-interval is N/n Independence: value of each random number is not affected by any other numbers 5
Bernoulli Variate A Bernoulli variate is useful for generating a binary outcome (0 or 1) to represent success (1) or failure (0) Example: wireless network packet transmission Example: coin flipping to produce heads or tails Bernoulli trial (with parameter p) p(1) = p, Random variate generation Generate ? If 0 < ? ?, ? = 1; Otherwise ? = 0 p(0) = 1 p 6
Inverse Transformation Method: Discrete Distributions Consider a tri-modal discrete distribution Example: size of an email message (in paragraphs, or KB) Example: p(1) = 0.5, p(2) = 0.3, p(3) = 0.2 Cumulative distribution function, F(x) 1.0 0.8 F(x) 0.5 0 1 2 3 x 7
Inverse Transformation Method: Discrete Distributions Algorithm Generate random number ? Random variate ? = ? if ? ? 1 < ? ?(?) Example: F(0) = 0, F(1) = 0.5, F(2) = 0.8, F(3) = 1.0 0 < u 0.5 variate ? = 1 0.5 < u 0.8 variate ? = 2 0.8 < u 1.0 variate ? = 3 8
Discrete Uniform Variate Discrete uniform (with parameters a and b) p(n) = 1/(b a + 1) for n = a, a + 1, , b F(n) = (n a + 1)/(b a + 1) Random variate generation Generate ? ? = ? + ?????(? ? ? + 1 ) OR ? = ? 1 + ???????(? ? ? + 1 ) 9
Geometric Variate Geometric (with parameter p) ? ? = ? 1 ?? 1, n = 1,2,3, Gives the number of Bernoulli trials until achieving the first success Random variate generation Generate ? ln ? ln 1 ? Geometric variate ? = 10
Inverse Transformation Method: Continuous Distributions Algorithm Generate uniform random number ? Solve ? ? = ? for random variate ? 1 F(x) u F(x): Cumulative Distribution Function of X = (? ?) 0 Variate ? x 11
Proof Define the random variable ? as: ? = ?(?) 1 ?(?) y x ? ? = ? ? = ? Therefore, ?~?(0,1) 12
Continuous Uniform Variate Uniform (with parameters a and b) b a 1/( = ) , a x b ( ) f x 0 otherwise. F(x) = (x a)/(b a), ? ? ? Random variate generation Generate ? ? = ? + ? ? ? 13
Exponential Variate Exponential (with parameter ?) f (x) = ? e-? x F(x) = 1 e-? x Random variate generation Generate ? 1 ? ln(?) ? = 1 ? ln(1 ?) Can also use ? = Note: If ? is Uniform(0,1), then 1 ? is Uniform(0,1) too! 14
Convolution Method Sum of n variables: ? = ?1+ ?2+ + ?? 1. Generate n random variate ??'s 2. The random variate ? is given by the sum of ?? s Example: the sum of two fair dice that are rolled P(x=2) = 1/36; P(x=3) = 2/36; P(x=4) = 3/36; P(x=5) = 4/36; P(x=6) = 5/36; P(x=7) = 6/36; P(x=8) = 5/36; P(x=9) = 4/36; P(x=10) = 3/36; P(x=11) = 2/36; P(x=12) = 1/36 15
Geometric Variate Geometric (with parameter p) ? ? = ? 1 ?? 1, n = 1,2,3, Gives the number of Bernoulli trials until achieving the first success let ? = 0, ? = 0 while (? == 0) Generate Bernoulli variate ? with parameter ? Geometric variate ? = ? + 1 Inefficient!! 16
Binomial Variate Binomial (with parameters p and ?) ? ???1 ?? ? , ? = 0,1, ,? ? ? = (? = ?) = Random variate generation Generate ? Bernoulli variates, ?1,?2, ,?? Binomial variate ? = ?1+ ?2+ + ?? 17
Poisson Variate Poisson (with parameter ?) ? ? = ? = ? =?? ?!? ?, ? = 0,1,2, Random variate generation (based on the relationship with exponential distribution) let ? = 0, ? = 0 while (? 1) Generate exponential variate y with parameter ? ? = ? + ? ? = ? + 1 Poisson variate ? = ? 1 18
Other Techniques: Normal Variate Normal (with parameters ? and ?2) 2 ? 2?? 1 ? ? ? 1 ? ? = , for ? + 2 Random variate generation using approximation method Generate two random numbers u1 and u2 Random variates ?1and ?2 are given by: ?1= ? + ? 2ln(?1) cos(2??2) ?2= ? + ? 2ln(?1) sin(2??2) 19
Empirical Distribution Could be used if no theoretical distributions fit the data adequately Example: Piecewise Linear empirical distribution Used for continuous data Appropriate when a large sample data is available Empirical CDF is approximated by a piecewise linear function: the jump points connected by linear functions 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 Piecewise Linear Empirical CDF 20
Empirical Distribution Piecewise Linear empirical distribution Organize ?-axis into ? intervals Interval ? is from ?? 1 to ?? for ? = 1,2, ,? ??: relative frequency of interval ? ??: relative cumulative frequency of interval ?, i.e., ??= ?1+ + ?? interval ? ?? 1 ?? ?0 ?? Empirical CDF: If ? is in interval ?, i.e., ?? 1< ? ??, then: ? intervals ? ? = ?? 1 + ??? ?? 1 where, slope ?? is given by ??=?? ?? 1 ?? ?? 1 21
Example Empirical Distribution Suppose the data collected for 100 broken machine repair times are: Interval (Hours) 0.0 < x 0.5 0.5 < x 1.0 1.0 < x 1.5 1.5 < x 2.0 Relative Frequency 0.31 0.10 0.25 0.34 Cumulative Frequency 0.31 0.41 0.66 1.00 i 1 2 3 4 Frequency 31 10 25 34 Slope 0.62 0.2 0.5 0.68 1 Piecewise Linear Empirical CDF 0.9 0.8 0.7 0.6 ?3 ?2 ?3 ?2= 0.5 Slope ?3= 0.5 0.4 0.3 0.2 0.1 0 0 ?0 0.5 ?1 1 ?2 1.5 ?3 2 ?4 22
Empirical Distribution Random variate generation: Generate random number ? Select the appropriate interval ? such that ?? 1< ? ?? Use the inverse transformation method to compute the random variate ? as follows 1 ??(? ?? 1) ? = ?? 1+ 23
Example Empirical Distribution Suppose the data collected for 100 broken machine repair times are: Interval (Hours) 0.25 < x 0.5 0.5 < x 1.0 1.0 < x 1.5 1.5 < x 2.0 Relative Frequency 0.31 0.10 0.25 0.34 Cumulative Frequency 0.31 0.41 0.66 1.00 i 1 2 3 4 Frequency 31 10 25 34 Slope 1.24 0.2 0.5 0.68 Suppose: ? = 0.83 ?3= 0.66 < ? ?4= 1.00 ? = 4 ? = ?3+1 ? ?3 ?4 1 = 1.5 + = 1.75 0.83 0.66 0.68 24
