Monte Carlo SimulationDiscrete-Event Simulation:A First CourseSection 2.3: Monte Carlo SimulationSection 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationSection 2.3: Monte Carlo SimulationWith Empirical Probability, we perform an experiment manytimes n and count the number of occurrences naof an eventAThe relative frequency of occurrence of event A is na/nThe frequency theory of probability asserts that the relativefrequency converges as n → ∞Pr(A) = limn→∞nanAxiomatic Probability is a formal, set-theoretic approachMathematically construct the sample space and calculate thenumber of events AThe two are compleme ntary!Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationExample 2.3.1Roll two dice and observe the up faces(1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6)(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6)(4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6)(5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6)(6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6)If the two up faces are summed, an integer-valued randomvariable, say X , is defined with possible values 2 through 12inclusivesum, x : 2 3 4 5 6 7 8 9 10 11 12Pr(X = x) :136236336436536636536436336236136Pr(X = 7) could be estimated by replicating the experimentmany times and calculating the relative frequency ofoccurrence of 7’sSection 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationRandom VariatesA Random Variate is an algorithmically generated realizationof a random variableu = Random() generates a Uniform(0, 1) random variateHow can we generate a Uniform(a, b) variate?0.0 u 1.0axbx = a + (b − a)u.................................................................................................................................................................................................................................................................Generating a Uniform Random Variatedouble Uniform(double a, double b) /* use a < b */ {return (a + (b - a) * Random());}Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationEquilikely Random VariatesUniform(0, 1) random variates can also be used to generate anEquilikely(a, b) random variate0 < u < 1 ⇐⇒ 0 < (b − a + 1)u < b − a + 1⇐⇒ 0 ≤ ⌊(b − a + 1)u⌋ ≤ b − a⇐⇒ a ≤ a + ⌊(b − a + 1)u⌋ ≤ b⇐⇒ a ≤ x ≤ bSpecifically, x = a + ⌊(b − a + 1) u⌋Generating an Equilikely Random Variatelong Equilikely(long a, long b) /* use a < b */ {return (a + (long) ((b - a + 1) * Random()));}Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationExamplesExample 2.3.3 To generate a random variate x that simulatesrolling two fair dice and summing the resulting up faces, usex = Equilikely(1, 6) + Equilikely(1, 6);Note that this is not equivalent tox = Equilikely(2, 12);Example 2.3.4 To select an element x at random from thearray a[0], a[1], . . ., a[n − 1] usei = Equilikely(0, n - 1); x = a[i];Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationGalileo’s DiceIf three fair dice are rolled, which sum is more likely, a 9 or a10?There are 63= 216 possible outcomesPr(X = 9) =25216∼=0.116 and Pr(X = 10) =27216= 0.125Program galileo calculates the probability of each p oss iblesum between 3 and 18The drawback of Monte Carlo simulation is that it onlyproduces an estimateLarger n does not guarantee a more accurate estimateSection 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationExample 2.3.6Frequency probability es timates converge slowly andsomewhat erratically0 100 200 300 400 500 600 700 800 900 1000Number of replications, n0.0850.0950.1050.1150.1250.1350.1450.1550.165Pr(X = 10)estimates◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦◦⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄⋄∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗Initial seed◦ – 12345⋄ – 54321∗ – 2121212You should always run a Monte Carlo simulation with multipleinitial seedsSection 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationGeometric ApplicationsGenerate a point at random inside a rectangle with oppositecorners at (α1, β1) and (α2, β2)α1x α2β1yβ2•(x, y)x = Uniform(α1, α2); y = Uniform(β1, β2);Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationGeometric ApplicationsGenerate a point (x, y) at random on the circumference of acircle with radius ρ and center (α, β)α xβy..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................•(x, y)ρ..............................................................................................................................................................θθ = Uniform(-π, π); x = α + ρ * cos(θ); y = β +ρ * sin(θ);Section 2.3: Monte Carlo Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Monte Carlo SimulationExample 2.3.8Generate a point (x, y) at random interior to the circle ofradius ρ centered at (α,