Monte-Carlo Theory and Examples

Class 2 Outline 1. Monte-Carlo: • Framework/Definition • Algorithm • Examples 2. Random Number Generation Monte-Carlo Framework Estimate q = E[ h(X) ] where X = {X1,…,Xm} is a random vector in Rm, h(.) is a function Rm -> R, and E[ | h(X) | ] < ¥ Monte-Carlo Algorithm 1. Generate n samples of X: X1, … , Xn 2. Compute h(X1), h(X2), …, h(Xn) 3. Estimate q = E[ h(X) ] with q = [h(X1)+h(X2)+…+h(Xn)]/n • Why is q a good estimator? A Sales Incentive Plan A company has a sales incentive plan with the following structure: In the months when sales are lower than $10,000, a salesrep get a base salary of $2000. If the monthly sales achieved are between $10,000 and $15,000, then he/she is paid 20% of the sales. Finally, if the monthly sales figure is larger than $15,000, the salesrep get 30% of the sales. Assuming the monthly sales achieved by a salesman follows an exponential distribution with mean $15,000, what is the mean and standard deviation of the salesman’s monthly salary under this compensation plan? Product Reliability • Consider a product reliability model given by: B A E C F D • Component life lengths: XA ~ exp(5.1); XB ~ N(4.5,1); XC ~ exp(6.5) XD ~ exp(5.4); XE ~ exp(6.4); XF ~ N(5.5,0.8) • What is the probability that the product will function for at least 3 years (warranty period)? DreamCast Launch Project Task A B C D E F G H I J K L M N O P Q R S T U V W Description Market Study External Developer Focus Group Feature Selection Hardware Engineering Operating System Devlpt. Advertising Campaign Supplier Selection & Negotiation Component Inventory Buildup Assembly Facility Setup Finished Good Inventory Buildup Library & Programmer Toolkit Devlpt. External Development Support Setup Internal Game Devlpt. External Game Devlpt. Platform Promotion Publisher Selection & Negotiation Website Setup Release Promotion Material Design Distribution Channels Devlpt. & Negotiation Carrier Selection & Negotiation Launch Event Organization & PR Hardware & Software Shipment Launch! Duration (weeks) 14 10 4 25 16 20 20 45 18 7 12 5 30 32 6 5 20 3 9 4 5 1 0 Precedence A,B C D,B D,M,N D G D I,H E K K L,O K M M D,M,N R S R J,T,P,N V,U,Q,F Setup Factory FG Inv Build I 18 G 14 Features C 4 B 10 Ext Dev Focus Grp V 7 1 45 D 25 20 Plan Launch Event HW Eng E 16 O/S Dev GO! Setup Comps Website H Inv Q 20 A 0 Ship HW & SW J Supp Sel & Neg Mkt Study W U Int Dev SW Dev Kit M K 5 30 Publisher Sel & Neg 12 Dev Supp O 6 Platform Mktg Distr Neg R L 5 5 P 3 N 32 Ext Dev S 9 T 4 Release Carrier Neg Promo F 20 Advert Plan Critical Path Algorithm 2 , 16 A 1. A task Early Start Date is the largest of all Early Finish Dates of its predecessors 14 5 , 15 B ES, EF D LS, LF 10 3 5 , 10 C LS, LF 5 ES, EF A LS, LF 2. A task Late Finish Date is the earliest of all Late Start Dates of its successors 14 ES, EF A 14 D 3 LS, LF 20, 34 ES, EF C 5 14, 19 LS, LF ES, EF B 10 15, 25 129, 129 W 43, 61 I 18 103,121 J G A 14 0,14 14, 18 C 4 14,18 0, 10 18, 43 25 18, 43 1 128, 129 H 101, 121 45 76, 121 20 Q 109,129 111, 116 43, 59 16 43, 59 10 4,14 20 56,76 71, 101 59, 71 M K 30 12 59, 71 79, 109 d LS, LF O 6 71, 77 5 124,129 P 5 123,128 111, 120 108, 111 L 71, 77 U 101, 106 71, 76 ES, EF A 129, 129 V 63, 108 D E B 124, 125 7 121,128 43, 63 0, 14 0 108, 115 5 72, 77 R N 3 112,115 32 77, 109 109, 129 77, 109 F 20 109, 129 S 9 115,124 120, 124 T 4 124,128 129, 129 W 43, 61 I 18 103,121 J G A 14 0,14 14, 18 C 4 14,18 0, 10 18, 43 25 18, 43 1 128, 129 H 101, 121 45 76, 121 20 Q 109,129 111, 116 43, 59 16 43, 59 10 4,14 20 56,76 71, 101 59, 71 M K 30 12 59, 71 79, 109 d LS, LF O 6 71, 77 5 124,129 P 5 123,128 111, 120 108, 111 L 71, 77 U 101, 106 71, 76 ES, EF A 129, 129 V 63, 108 D E B 124, 125 7 121,128 43, 63 0, 14 0 108, 115 5 72, 77 R N 3 112,115 32 77, 109 109, 129 77, 109 F 20 109, 129 S 9 115,124 120, 124 T 4 124,128 Critical Path Solution Task A B C D E F G H I J K L M N O P Q R S T U V W Description Market Study External Developer Focus Group Feature Selection Hardware Engineering Operating System Devlpt. Advertising Campaign Supplier Selection & Negotiation Component Engineering & Inventory Buildup Assembly Facility Setup Finished Good Inventory Buildup Library & Programmer Toolkit Devlpt. External Development Support Setup Internal Game Devlpt. External Game Devlpt. Platform Promotion Publisher Selection & Negotiation Website Setup Release Promotion Material Design Distribution Channels Devlpt. & Negotiation Carrier Selection & Negotiation Launch Event Organization & PR Hardware & Software Shipment Launch! Duration (weeks) Precedence LS LF ES 14 -129 -115 -129 10 -125 -115 -129 4 A,B -115 -111 -115 25 C -111 -86 -111 16 D,B -86 -70 -86 20 D,M,N -20 0 -20 20 D -73 -53 -86 45 G -53 -8 -66 18 D -26 -8 -86 7 I,H -8 -1 -21 12 E -70 -58 -70 5 K -57 -52 -58 30 K -50 -20 -58 32 L,O -52 -20 -52 6 K -58 -52 -58 5 M -6 -1 -28 20 M -20 0 -28 3 D,M,N -17 -14 -20 9 R -14 -5 -17 4 S -5 -1 -8 5 R -5 0 -17 1 J,T,P,N -1 0 -4 0 V,U,Q,F 0 0 0 EF Slack -115 0 -119 4 -111 0 -86 0 -70 0 0 0 -66 13 -21 13 -68 60 -14 13 -58 0 -53 1 -28 8 -20 0 -52 0 -23 22 -8 8 -17 3 -8 3 -4 3 -12 12 -3 3 0 0 Stochastic Task Durations Task A B C D E F G H I J K L M N O P Q R S T U V W Description Duration (weeks) Precedence LS LF ES EF Slack Market Study 14 -129 -115 -129 -115 0 External Developer Focus Group 10 -125 -115 -129 -119 4 Feature Selection 4 A,B -115 -111 -115 -111 0 Hardware Engineering 25 C -111 -86 -111 -86 0 Operating System Devlpt. 16 D,B -86 -70 -86 -70 0 Advertising Campaign 20 D,M,N -20 0 -20 0 0 Supplier Selection & Negotiation 20 D -73 -53 -86 -66 13 Component Engineering & Inventory Buildup 45 G -53 -8 -66 -21 13 Assembly Facility Setup 18 D -26 -8 -86 -68 60 Finished Good Inventory Buildup 7 I,H -8 -1 -21 -14 13 Library & Programmer Toolkit Devlpt. 12 E -70 -58 -70 -58 0 External Development Support Setup 5 K -57 -52 -58 -53 1 Internal Game Devlpt. 30 K -50 -20 -58 -28 8 External Game Devlpt. 32 L,O -52 -20 -52 -20 0 Platform Promotion 6 K -58 -52 -58 -52 0 Publisher Selection & Negotiation 5 M -6 -1 -28 -23 Duration of development tasks E, M and N22 Website Setup 20 M -20 0 -28 -8 8 now follow exponential distributions with Release Promotion Material Design 3 D,M,N -17 -14 -20 -17 3 Distribution Channels Devlpt. & Negotiation means 16, 309 and 32 respectively. R -14 -5 -17 -8 3 Carrier Selection & Negotiation 4 S -5 -1 -8 -4 3 Launch Event Organization & PR 5 R -5 0 -17 -12 12 What is the probability that the total project Hardware & Software Shipment 1 J,T,P,N -1 0 -4 -3 3 duration will be more than 135 weeks? Launch! 0 V,U,Q,F 0 0 0 0 0 Stochastic Programming Distribution Centers (j) Plants (i) X1 Cap1 Capacity Cij Cap2 X2 Demand X3 Transportation Unit Costs Stochastic Demand X1~N(1500,350) X2~N(2000,600) X3~N(1500,450) Random Number Generation • The key in a Monte-Carlo simulation is to generate sample values drawn from a known probability distribution. How is this done? Generate Sample Value from Uniform[0,1] Discrete Distribution Continuous Distribution • Inverse transform method • Rejection method • Inverse transform method • Rejection method • Composition method • Polar method U[0,1] Sample Generation 1. Calculate Z1, Z2,… given by the Linear Congruential Generator: Zi = ( aZi-1 + c ) modulo m where m, a, c and Z0 are non-neg. integers modulus seed 2. Take Ui = Zi / m as a proxy to an independent sequence of U[0,1] random variates (note: 0 £ Ui £ 1 for all i) Linear Congruential Generator • Example: Zi = ( 11Zi-1 ) modulo 16 Z0 = 1 Z1 = (11) mod 16 = 11 Z2 = (121) mod 16 = 9 Z3 = (99) mod 16 = ? Z4 = (33) mod 16 = ? • Huge literature on LCG periods, parameter choice, statistical tests for randomness… • Crystal Ball uses Zi = (630,360,016 Zi-1 ) mod (231-1) Discrete Distributions • We want to simulate a random variable X defined by P( X = xj ) = pj, j=0,1,…,m 1. Generate a sample U from U[0,1] 2. if U < p0 then X = x0 if p0 < U < p0 + p1 then X = x1 ….. if p0 + … + pj-1 < U < p0 + … + pj then X = xj • Why does this work? Solution 1. 2. Generate a sample U from U[0,1] if U < p0 then X = x0 if p0 < U < p0 + p1 then X = x1 ….. if p0 + … + pj-1 < U < p0 + … + pj then X = xj • P( X = xj ) = P(p0 + … + pj-1 < U < p0 + … + pj ) = pj Continuous Distributions • We want to simulate a random variable X defined by P( X < t ) = F(t) (F inversible) 1. Generate a sample U from U[0,1] 2. Set X = F-1( U ) • Why does this work? Solution 1. Generate a sample U from U[0,1] 2. Set X = F-1( U ) • P ( X < t ) = P( F-1(U) < t ) = P( U < F(t) ) = F(t) F(x) 1 U[0,1] 0 F-1( U) x Exponential Distribution • Variable exp(l) has cdf. F(t) = 1 – exp(-lt); F-1(y) = - log(1-y) / l 1. Generate U from U[0,1] 2. Compute X = - log(1-U ) / l 3. The distribution of X is exp(l) ! Class 2 Wrap-Up 1. Monte-Carlo Framework, Algorithm & Examples 2. Crystal Ball Modeling 3. Theory of Random Number Generation