Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkDiscrete-Event Simulation:A First CourseSection 2.4: Monte Carlo Simulation ExamplesSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkOutlineOverviewMatrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkSection 2.4: Monte Carlo Simulation ExamplesRecall that axiomatic and experimental approaches arecomplementarySlight changes in assumptions can sink an axiomatic solutionIn other cases, an axiomatic solution is intractableMonte Carlo simulation can be used as an alternative in eithercaseFour more examples of MC simulation are presented hereSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkExample 1: Matrices and DeterminantsMatrix: set of real or complex numbers in a rectangular arrayFor matrix A, aijis the element in row i, column jA =a11a12. . . a1na21a22. . . a2n............am1am2. . . amnHere, A is m × n — m rows, n columnsInteresting quantities: eigenvalue, trace, rank, determinantSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkDeterminantsThe determinant of a 2 × 2 matrix A is|A| =a11a12a21a22= a11a22− a21a12The determinant of a 3 × 3 matrix A is|A| =a11a12a13a21a22a23a31a32a33= a11a22a23a32a33− a12a21a23a31a33+ a13a21a22a31a32Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkRandom MatricesRandom matrix: matrix whose elements are random variablesConsider a 3 × 3 matrix whose elements are random withpositive diagonal, negative off-diagonal elementsQuestion: What is the probability the determinant is positive?+u11−u12−u13−u21+u22−u23−u31−u32+u33> 0Axiomatic solution not easily calculatedSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkSpecification ModelLet event A be that the determinant is positiveGenerate N 3 × 3 matrices with random elementsCompute the determinant for each matrixLet na= number of matrices with determinant > 0Probability of interest: Pr(A)∼=na/NSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkComputational Model: Program detdetfor (i = 0; i < N; i++) {for (j = 1; j <= 3; j++) {for (k = 1; k <= 3; k++) {a[j][k] = Random();if (j != k)a[j][k] = -a[j][k];}}temp1 = a[2][2] * a[3][3] - a[3][2] * a[2][3];temp2 = a[2][1] * a[3][3] - a[3][1] * a[2][3];temp3 = a[2][1] * a[3][2] - a[3][1] * a[2][2];x = a[1][1]*temp1 - a[1][2]*temp2 + a[1][3]*temp3;if (x > 0)count++;}printf(‘‘%11.9f’’, (double) count / N);Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkOutput From detWant N sufficiently large for a good point estimateAvoid recycling random number sequencesNine calls to Random() per 3 × 3 matrix =⇒ N ¡ m / 9∼=239 000 000For initial seed 987654321 and N = 200 000 000,Pr(A)∼=0.05017347Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkPoint Estimate ConsiderationsHow many significant digits should be reported?Solution: run the simulation multiple timesOne option: Use different initial seeds for each runCaveat: Will the same sequences of random numbers appear?Another option: Use different a for each runCaveat: Use a that gives a good random sequenceFor two runs with a = 16807 and 41214Pr(A)∼=0.0502Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkExample 2: CrapsToss a pair of fair dice and sum the up facesIf 7 or 11, win immediatelyIf 2, 3, or 12, lose immediatelyOtherwise, sum becomes “point”Roll until point is matched (win) or 7 (loss)What is Pr(A), the probability of winning at craps?Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkCraps: Axiomatic SolutionRequires conditional probabilityAxiomatic solution: 244/495∼=0.493Underlying mathematics must be changed if assumptionschangeE.g., unfair diceAxiomatic solution provides a nice consistency check for(easier) Monte Carlo simulationSection 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkCraps: Specification ModelModel one die roll with Equilikely(1, 6)Algorithm 2.4.1wins = 0;for (i = 1; i <= N; i++) {roll = Equilikely(1, 6) + Equilikely(1, 6);if (roll = 7 or roll = 11)wins++;else if (roll != 2 and roll != 3 and roll != 12) {point = roll;do {roll = Equilikely(1, 6) + Equilikely(1, 6);if (roll == point) wins++;} while (roll != point and roll != 7)}} return (wins/N);Section 2.4: Monte Carlo Simulation Examples Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Matrices and DeterminantsCrapsHatcheck GirlStochastic Activity NetworkCraps: Computational ModelProgram craps: uses switch statement to determine rollsFor N = 10 000 and three different initial seeds (see text)Pr(A) = 0.497, 0.485, and 0.502These results are consistent with 0.493 axiomatic solutionThis (relatively) high probability is attractive to gamblers,yet ensures the house will win in the long runSection 2.4: Monte Carlo Simulation