### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for EMSE 273 with Professor Dorp at GW (3)

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Department

This 27 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 19 views.

## Reviews for Class Note for EMSE 273 with Professor Dorp at GW (3)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/07/15

EMSE 273 Discrete System Simulation 7 RANDOM NUMBER GENERATION 71 Properties of Random Numbers A sequence of random numbers R1Rn must have two important statistical properties Uniformity and Independence Each R2 should be an independent realization or sample from a R N U0 1 variable fx 1 0 1 X ER folxdzr a 2 VarltRgt 101x lERl2 w3l l l2 i Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Consequences of Uniformity and Independence Properties 1 If the interval 01 is divided into n subinterval of equal length the expected number of observations in each interval is Nn where N is the total number of observations 2 The probability of observing a value in a particular interval is independent of the previous values drawn 72 Generation of PseudoRandom Numbers quotPseudoquot means false so false random numbers are being generated If the method is known the numbers cannot be truly random The goal of any generation scheme is to quotimitatequot the real properties of a uniform distribution and independence as closely as possible Lecture Notes by JR van Dorp 2 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Problems that can occur with Pseudo Random Numbers 1 NonUniformity 2 Numbers are discrete valued and not continuous on 01 3 The mean of generated numbers 7A ER 2 4 The variance of generated numbers 7A VarR 11 2 5 There may be dependence For Example a Autocorrelation between numbers b Numbers Successiver higher or lower than adjacent numbers 0 Several Numbers above the mean are followed by several number below the mean Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Usually pseudorandom numbers are generated by a computer as part of the simulation Numerous methods are available In selecting a routine there are a number of important considerations 1 The routine should be fast 2 The routine should be platform independent and portable between different programming languages 3 The routine should have a sufficiently long cycle much longer than the required number of samples 4 The random numbers should be replicable Usefull for debugging and variance reduction techniques 5 Most importantly the routine should closely approximate the ideal statistical properties Lecture Notes by JR van Dorp 4 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Inventing techniques that seem to generate random number is easy inventing techniques that really produce sequences that appear to independent uniformly distributed is incredibly difficult 73 Techniques for Generating Random Numbers The linear congruential method is most widely known Will also report an extension that yield sequences with a longer period 731 Linear Congruentia Method Generates a sequence X1 X2 X3 using XZH aXZ39 l 0 mod m 71 Lecture Notes by JR van Dorp 5 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation where X0 is called the seed variable a is the constant multiplier c is the increment and m is the modulus When 0 7A 0 c 0 71 is referred to as the mixed congruential method multiplicative congruential method The selection of the valeus for a c m and X0 drastically affect the statistical properties and the cycle length Variations of 71 are quite common in computer packages EXAMPLE 71 X0 27 a 17 c 43 and m 100 Here integer values will be between 0 and 99 because of the modulus m Note that random integers are being generated rather than random numbers These integers should be uniformly distributed Convert to numbers in 01 by normalizing with modulus m Xi R m 72 Lecture Notes by JR van Dorp 6 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation X0 27 X1 17 27 43 mod 100 502 mod 100 2 R1 002 X2 17 2 l 43 mod 100 77m0d 100 77 R2 077 etc Of primary importance is uniformity and statistical independence Of secondary importance is maximum density and maximum period within the sequence ampi12 Note that the sequence can only take values in 0 1m2m m 1m 1 Thus R2 is discrete rather than continuous Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation This is easy to fix by choosing large modulus m Values such as m 231 1 and m 248 are in common use in generators appearing in many simulation languages Maximum Density and Maximum period can be achieved by the proper choice of a c m and X0 For m a power of 2 say m 2b and 0 7A 0 the longest period P m 2b is achieved provided 0 is a relative prime to m that is the greates common factor of c and m is 1 and a 1 4 k where k is an integer For m a power of 2 say m 2b and c 0 the longest period P m4 25 2 is achieved provided the seed X0 is odd and the multiplier a38kforsomek 201 For m is a prime number and c 0 the longest period P m 1 is achieved provided the multiplier a has the property that the smallest integer k such that ak 1 is divisible by m is k m 1 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation EXAMPLE 72 a 11 m 26 64 c 0 and X0 123and 4 EXAMPLE 73 a 19 m 102 100 c 0 and X0 63 EXAMPLE 74 a 75 16807 m 231 1 c 0 This one is in actual use and extensively tested Conditions ensure a period P m 1 By Changing X0 the user can control repeatibility of sequence k0 Xk Rk Gap 0 1234567 1 1422014746 00006 06616 2 456328559 06622 04497 3 849987676 02125 01833 4 681650688 03958 00784 5 1825340118 03174 05326 6 1687465831 08500 00642 7 1569179335 07858 00551 8 2097898185 07307 02462 9 1988278849 09769 00510 10 9584176 09259 09214 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Over 500 Samples Average 0499 Variance 0086 Average Gap 0002 Emperical CDF of LCG Generator over 500 Samples 1000 0900 0800 0700 0600 u 00500 0 0400 0300 0200 0100 0000 00000 01000 02000 03000 04000 05000 06000 07000 08000 09000 10000 r Emperical CDF Uniform CDF Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 10 EMSE 273 Discrete System Simulation 732 Combined Linear Congruentia Method Random Number Generator of Example 74 with a period of 231 1 is 2 109 is no longer adequate with current advancements of computing powers Area of new research is deriving generators with longer periods See L39Ecuyer 1998 This research uses the following important result lf W231 Wm WM are independent discrete valued random variables not necesarrily identical distributed but one of them say WM is uniformly distributed on the integers 0 m1 2 then k lVZ mod m1 1 j1 is uniformly distributed on the integers 0 m1 1 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 11 EMSE 273 Discrete System Simulation 1 Let X231 X232 Xiyk be the ith output from k different multiplicative c 0 congruential generators where first generator has modulus m1 and the multiplier a1 chosen so that the period is m1 1 2 The first generator then produces X231 that are approximately uniform distributed on 1m1 1 3 Hence WM 2 X231 1 are approximately uniform distributed on 0 m1 2 L39Ecuyer suggest combined generators of the form Xi 1j1X 7j mod m1 j1 with X2 gt 0 R2 11 Lecture Notes by JR van Dorp 12 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Note that the 1j 1 coefficient implicitly perform the subtraction Xi 1 For example if k 2 10X 1 1 11X2392 1 Z 1j1X239j j1 Maximum possible period for such a generator is k HOW1 which is achieved by the following generator Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 13 EMSE 273 Discrete System Simulation EXAMPLE 75 1 Selected seed X110 6 12147483562 Selected seed X270 6 121474833398 2 Evaluate each individual generator X17j1 39 lej mod 3 Set Xj1 X17j1 X2J1gt mod 4 Return 214333563 Xj gt 0 Rjtl 2147483562 X 0 2147483563 j 5 Setj j 1 and go to Step 2 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 14 EMSE 273 Discrete System Simulation ARENA RANDOM NUMBER GENERATOR 1403580An2 810728An3 mod 4294967087 An Bn 527612Bn1 1370589Bn3 mod 4294944443 Zn 2 An B mod 4294967087 4294967087 Zn 2 0 Zn 4294967088 Z gt 0 Un 4294967088 Seed a sixvector of first three An s Bn s Lecture Notes by JR van Dorp 15 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 74 Tests for Random Numbers Desirable Properties Uniformity and Independence 1 Frequency Test Uses the KolmogorovSmirnic or the ChiSquare Test to compare the distribution of the set of numbers to a uniform distribution 2 Runs Test Test the runs up and down or the runs above and below the mean by comparin the actual values to expected values The Statistics for comparison is the chisquare test 3 Autocorrelation Test Test the correlation between numbers and compares the sample correlation to the expected correlation of zero 4 Gap Test Counts the number of digits that appear between repetitions of a particular digit and then uses the Kolmogorov Smirnov test to compare with the expected sized of the gaps 5 Poker Test Treat numbers grouped together as a poker hand Then the hands obtained are compared to what is expected using the chisquare test First Entry test for Uniformity Second through Fifth Entry tests for Independence Lecture Notes by JR van Dorp 16 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 741 Frequency Tests 1 The Kolmogorov Smirnov Test Test compares a continuous cdf Fr to an emperical cdf SNr of the sample of N observations Step 1 Determine Order Statistics Define 0 L S R SNCT Ra S if lt R2 17Z 17 1 r 2 R Step 2 Compute D Mam SNr via 10 E oo 00 73 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 17 EMSE 273 Discrete System Simulation Fxx Uniform CDF R04 R0 R01 D Max i RD Mam R 3 1 1 igN N 0 1 iltN Z N Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 18 EMSE 273 Discrete System Simulation Step 3 Compute for significant level oz 2 010 005 or 001 for N 2 35 122 136 163 D D D 010 005 001 Step 4 Test Hypothesis D 3 Da Accept No Difference between SNr and Fr D gt Da Reject No Difference between SNr and Fr Lecture Notes by JR van Dorp 19 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 2 The Chisquare Test The chisquare test uses the sample statistic 2 n 0239 E02 X0 2 where Oi is the observed number in the ith class E is the expected number in the ith class and n is the number of classes Step 1 Determine Order Statistics RU S Ra S S RN 73 Step 2 Divided Range Rm Rm in n equidistant intervals ah bi such that each interval has at least 5 observations Step 3 Calculate for 239 1 N 0239 N 39 SNOW SN02397 E239 N 39 F090 Fai Lecture Notes by JR van Dorp 20 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Step 4 Calculate Step 5 Determine for significant level oz X37714 X3 3 X27714 Accept No Difference between SNr and Fr X3 gt X27714 Reject Difference between SNr and Fr 742 Runs Test 008 009 023 011 016 018 002 009 030 012 013 029 Both KS and ChiSquare test would accept the above sample as from a uniform but if we look at the sample above column wise we see that each column is strictly larger than the other Hence independence may be an issue in that case Lecture Notes by JR van Dorp 21 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 1 Runs up and Runs Down The runs test examines the arrangement of numbers in a sequence to test the hypothesis of independence A run is defined as a succesion of similar events preceded and follow by a different event Length of the run is the number of events that occur in the run EXAMPLE Series of coin Tosses H TTH H TTTH T Run 1 has length 1 Run 2 has lenght 2 Run 3 has length 2 Run 4 has length 3 Run 5 has length 1 Run 6 has length 1 TWO CONCERNS in a Runs Test 1 The number of Runs 2 The length of the Runs An up run is a sequence of numbers which is succeeded by a larger number A down run is a sequence of numbers each of which is succeeded by a smaller number Lecture Notes by JR van Dorp 22 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Example 1 Example 2 Example 3 087 008 008 015 018 093 023 023 015 045 036 096 069 042 026 032 055 084 03 063 028 019 072 079 024 089 036 018 091 057 065 082 093 022 081 Runs 8 Runs 1 Runs 9 Runs up 4 Runs up 1 Runs up 5 Runs Down 4 Runs Dowr 0 Runs Down 4 Example 2 and Example 3 are two extremes If N is the number of observation the maximum number of runs is N 1 and the minimum number of runs is 1 If a is the number of runs in an independent sequence of uniform numbers the mean and the variance of a is given by Lecture Notes by JR van Dorp 23 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 2N 1 216N 29 3 06 90 Ma For N gt 20 the distribution of a is well approximated by a Normal distribution N Ma 0393 STEP 1 Calculate number of runs a STEP 3 Determine acceptence region 2 2 from a N0 1 distribution STEP 2 Calculate STEP 4 Accept Independence Reject Independence Lecture Notes by JR van Dorp 24 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation 2 Runs above and below the mean Acceptance of the indepence following the previous test is necessary but not sufficient condition An independent sequence should not contain long runs with observations above the mean and below the mean Let b the total number of runs above or below the mean and m be the number of observations above the mean and n2 be the number of observations below the mean Note that the maximum number of runs is N 2 m M and the minimum number of runs is 1 Given m and n2 2711712 1 2 2n1n22n1n2 b N 2 b N2N 1 and if m gt 20 or m gt 20 b is approximately normal distributed STEP 1 Calculate number of runs 12 Lecture Notes by JR van Dorp 25 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation STEP 2 Calculate ml ZZb Mb a N 2 Ob W N2N 1 STEP 3 Determine acceptence region 2 2 from 3 N0 1 distribution STEP 4 Accept Independence Z ZZ Reject Independence 26 Lecture Notes by JR van Dorp Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7 EMSE 273 Discrete System Simulation Homework 1 Implement the The KomogorovSmirnov Test in these notes for a random sample of 100 numbers generated by the RAND function in EXCEL and test the hypothesis whether we accept or reject uniformity of the random numbers generated by the RAND function Homework 2 Implement the Chisquare Test in these notes for a random sample of 100 numbers generated by the RAND function in EXCEL and test the hypothesis whether we accept or reject uniformity of the random numbers generated by the RAND function Use 10 bins or classes Lecture Notes by JR van Dorp 27 Source Discrete Event Simulation by Banks Carson and Nelson Chapter 7

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.