[SOLVED] COMP9334 2

Capacity Planning for Computer Systems and Networks
Week 5B_2: Discrete event simulation (4): Generating random numbers

This lecture

Copyright By Assignmentchef assignmentchef

Discrete event simulation
Week4B:Howtostructurethesimulation Weeks5A,5B_1:Statisticalanalysis
This lecture
Backgroundonrandomnumbersandhowtheyaregenerated
Howtogeneraterandomnumbersofanyprobabilitydistribution Reproducibility
Motivation
ThePythonrandomlibrarycangeneraterandomnumbersfrom many probability distributions but sometimes you may need a distribution that the library does not have
T1,2022 COMP9334 2

Random number generator in C
In C, the function rand() generates random integers between 0 and RAND_MAX
E.g. The following program generates 10 random integers:
Let us generate 10,000 random integers using rand() and see how they are distributed
#include #include
int main () {
for (i = 0; i < 10; i++) printf(“%d
“,rand());This C file genrand1.c is available from the course web site. T1,2022 COMP9334Distribution of 10000 entries from rand()Sort into 50 binsIf the numbers are really uniformly distributed, we expect 200 numbersin each bin.The numbers are almost uniformly distributed T1,2022 COMP9334 4 TherandomnumbergeneratorinCisaLinearCongruentialGenerator (LCG) LCG generates a sequence of integers {Z1, Z2, Z3, …} according to the recursionZk =aZk-1 +c(modm) where a, c and m are integers Bychoosinga,c,m,Z1appropriately,wecanobtainasequenceof seemingly random integers Ifa=3,c=0,m=5,Z1 =1,LCGgeneratesthesequence1,3,4,2,1, 3, 4, 2, … Fact:ThesequencegeneratedbyLCGhasacycleofm-1 Wemustchoosemtobealargeinteger ForC,m=231 Thepropernameforthenumbersgeneratedispseudo-randomT1,2022 COMP9334 5 LCG generates a sequence of integers {Z1, Z2, Z3, …} according to the recursionZk =aZk-1 +c(modm) where a, c and m are integers The term Z1 is call a seed Bydefault,Calsouses1astheseedanditwillgeneratethesamerandom sequence However,sometimesyouneedtogeneratedifferentrandom sequences and you can change the seed by calling the function srand() before using rand() Demo genrand1.c, genrand2.c and genrand3.m genrand1.c uses the default seed genrand2.c sets the seed using command line argument genrand3.c sets the seed using current timeT1,2022 COMP9334 6Uniformly distributed random numbers between (0,1) With rand() in C, you can generate uniformly distributed random numbers in between 1 and 231-1(= RAND_MAX) BydividingthenumbersbyRAND_MAX,yougetrandomlydistributed numbers in (0,1) In Python, uniformly distributed random numbers in (0,1) can be generated by random.random() or numpy.random.random() BothlibrariesusestheMersenneTwisterrandomnumbergenerator with a period of 219937 – 1 If you use 109 random number in a second, the sequence will only repeat after 105985 years Why are uniformly distributed random numbers important? Ifyoucangenerateuniformlydistributedrandomnumbersbetween(0,1), you can generate random numbers for any probability distributionT1,2022 COMP9334 7Random numbers generated by numpy 10,000 numbers generated by numpy.random.random() Codeinrand_uni.py T1,2022 COMP9334 8Fair coin distribution You can generate random numbers between 0 and 1 You want to use these random numbers to imitate fair coin tossing, i.e. ProbabilityofHEAD=0.5 ProbabilityofTAIL=0.5 You can do this using the following algorithm Generatearandomnumberu Ifu<0.5,outputHEAD Ifu0.5,outputTAILT1,2022 COMP9334 9A loaded die You want to create a loaded die with probability mass function 0.3 The algorithm is: Generatearandomnumberu If u<0.1,output1 If0.1u<0.3,output2 If0.3u<0.4,output3 If0.4u<0.7,output4 If0.7u<0.8,output5 If0.8u ,output6 T1,2022 COMP9334Cumulative probability distribution 6 Probability that the dice gives a value x Ex: Can you work out what these levels should beT1,2022 COMP9334 Comparing algorithm with cumulative distribution The algorithm is: Generatearandomnumberu If u<0.1,output1 If0.1u<0.3,output2 If0.3u<0.4,output3Ex: What do 1 If0.4u<0.7,output4 If0.7u<0.8,output5 If0.8u ,output6Probability that the die gives a value x you noticeintervals in 0.4 the algorithm 0.3 and the 0.1 cumulative distribution?Graphical interpretation of the algorithm The algorithm is: Generatearandomnumberu If u<0.1,output1 If0.1u<0.3,output2 If0.3u<0.4,output3Ex: Let us 1 If0.4u<0.7,output4 If0.7u<0.8,output5 If0.8u ,output6Probability that the die gives a value xu = 0.5126, what should the algorithm output?Graphical representation of inverse transform method Consider the cumulative density function (CDF) y = F(x), showed in the figure belowFor this particular F(x), if u = 0.7 is generatedthen F-1(0.7) is 6.8 T1,2022 COMP9334 14Inverse transform method Amethodtogeneraterandomnumberfromaparticulardistributionis the inverse transform method Ingeneral,ifyouwanttogeneraterandomnumberswithcumulative density function (CDF) F(x) = Prob[X x], you can use the following procedure: Generateanumberuwhichisuniformlydistributedin(0,1) ComputethenumberF-1(u) Example: Let us apply the inverse transform method to the exponential distribution CDFis1-exp(-lx)T1,2022 COMP9334 15Generating exponential distribution Givenasequence{U1,U2,U3,…}whichisuniformlydistributedin(0,1) Thesequence-log(1-Uk)/lisexponentiallydistributedwithratel (Python file hist_expon.py)1. Generate 10,000 uniformlydistributed numbers in (0,1)2. Compute -log(1-uk)/2 where uk are the numbers generated in Step 13. The plot shows1. The histogram of the numbers generated in Step 2 in 50 bins2. The red line show the expected number of exponential distributed numbers in each bin T1,2022 COMP9334 16Reproducible simulation motivation You may recall that when we run the simulation sim_mm1.py, each simulation run gives a different result because different set of random numbers is used Doing simulation is like performing a scientific experiment Good science demands reproducibility E.g.,Ifyouclaimthatthemeanresponsetimeofasimulationrunis say 1.3579, other people should be able to reproduce your resultT1,2022 COMP9334 17Reproducible simulation In order to realise reproducibility of results, you need to save the state of the random number generator before simulation If you reuse the setting later, you can reproduce the result ThestateoftheMersenneTwisterplaysasimilarroletoaseedinthe generator used by C Demo: sim_mm1.py# obtain setting and save it in a filerand_state = random.getstate()pickle.dump( rand_state, open( “rand_state_mm1.p”, “wb” ) ) # load the saved setting and apply itrand_state = pickle.load( open( “rand_state_mm1.p”, “rb” ) ) random.setstate(rand_state) T1,2022 COMP9334 18Random number generators in Python Although both the random and numpy.random libraries use the Mersenne Twister generator, the generator for the libraries are separate The numpy.random library Youcangenerateanarrayofrandomnumbers Thefunctionstogetandsetthestateare numpy.random.get_state() and numpy.random.set_state() FewerdistributionscomparedtotherandomlibraryT1,2022 COMP9334 19 Basic concepts on pseudo-random number generators Using the inverse transform method to produce randomnumbers of different probability distributions Reproducibility why and howT1,2022 COMP9334 20References Generation of random numbers RajJain,TheArtofComputerSystemsPerformanceAnalysisSections 26.1 and 26.2 on LCGSection 28.1 on the inverse transform methodsCOMP9334 21 CS: assignmentchef QQ: 1823890830 Email: [email protected]