Capacity Planning for Computer Systems and Networks
Week 5B_2: Discrete event simulation (4): Generating random numbers
This lecture
Copyright By PowCoder代写加微信 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
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• Ifu≥0.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.1≤u<0.3,output2 • If0.3≤u<0.4,output3• If0.4≤u<0.7,output4 • If0.7≤u<0.8,output5 • If0.8≤u ,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.1≤u<0.3,output2 • If0.3≤u<0.4,output3Ex: What do 1• If0.4≤u<0.7,output4 • If0.7≤u<0.8,output5 • If0.8≤u ,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.1≤u<0.3,output2 • If0.3≤u<0.4,output3Ex: Let us 1• If0.4≤u<0.7,output4 • If0.7≤u<0.8,output5 • If0.8≤u ,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,“TheArtofComputerSystemsPerformanceAnalysis”Sections 26.1 and 26.2 on LCGSection 28.1 on the inverse transform methodsCOMP9334 21程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.