Transcription
Simulation, 3rd EditionSolution of Exercise ProblemsYan ZengSeptember 3, 2008
Contents1 Introduction32 Elements of Probability63 Random Numbers144 Generating Discrete Random Variables195 Generating Continuous Random Variables326 The Discrete Event Simulation Approach377 Statistical Analysis of Simulated Data388 Variance Reduction Techniques399 Statistical Validation Techniques4010 Markov Chain Monte Carlo Methods4111 Some Additional Topics421
This is a solution manual for the textbook Simulation, 3rd Edition, by Sheldon M. Ross (2002, AcademicPress). This version omits the Problem 8, 9, 18 of Chapter 4.2
Chapter 1Introduction1. (a)Proof. The Matlab code for the problem solution is given below.function departureTimes ross 1 1a(arrivalTimes, serviceTimes)%ROSS 1 1a%%%solves Exerciese Problem 1(a) of Chapter 1, [1].Reference:[1] Ross: Simulation, Third Edition, Academic Press, 2002.if (numel(arrivalTimes) numel(serviceTimes))error(’Array of arrival times and array of service times must have same size’);endnumCustomers numel(arrivalTimes);serverEmptyTime 0;% The time when the server is empty.departureTimes zeros(1, numCustomers);for i 1:numCustomersif (serverEmptyTime arrivalTimes(i))departureTimes(i) arrivalTimes(i) serviceTimes(i);elsedepartureTimes(i) serverEmptyTime serviceTimes(i);endserverEmptyTime departureTimes(i);end(b)Proof. The Matlab code for the problem solution is given below.function departureTimes ross 1 1b(arrivalTimes, serviceTimes)%ROSS 1 1b%%%solves Exerciese Problem 1(b) of Chapter 1, [1].Reference:[1] Ross: Simulation, Third Edition, Academic Press, 2002.3
if (numel(arrivalTimes) numel(serviceTimes))error(’Array of arrival times and array of service times must have same size’);endnumCustomers numel(arrivalTimes);numServers 2;serverEmptyTimes zeros(1, numServers); % serverEmptyTimes(i) is the time% when the i-th server is empty.departureTimes zeros(1, numCustomers);for i 1:numCustomers% serverTime is the earliest time when a server is empty; serverNo is% this server’s number (1 or 2).[serverTime, serverNo] min(serverEmptyTimes);if (serverTime arrivalTimes(i))departureTimes(i) arrivalTimes(i) serviceTimes(i);elsedepartureTimes(i) serverTime serviceTimes(i);endserverEmptyTimes(serverNo) departureTimes(i);end(c)Proof. The Matlab code for the problem solution is given below.function departureTimes ross 1 1c(arrivalTimes, serviceTimes)%ROSS 1 1c%%%solves Exerciese Problem 1(c) of Chapter 1, [1].Reference:[1] Ross: Simulation, Third Edition, Academic Press, 2002.if (numel(arrivalTimes) numel(serviceTimes))error(’Array of arrival times and array of service times must have same size’);endnumCustomers numel(arrivalTimes);serverEmptyTime 0; % The time when the server is emptydepartureTimes zeros(1, numCustomers);unserved ones(1, numCustomers); % unserved(i) has value 1 if the i-th customer has% not been served, and value 0 otherwise.while ( sum(unserved) 0 ) % sum(unserved) 0 iff there are customers unserved.% Find the customer who has been waiting the least time. If no customer% is waiting, get the next customer to arrive.waitingCustomers ( (arrivalTimes serverEmptyTime) & unserved );if ( sum(waitingCustomers) 0 ) % There are no customers waiting.[temp, next] max(arrivalTimes serverEmptyTime);departureTimes(next) arrivalTimes(next) serviceTimes(next);4
else % There are customers waiting.[temp, next] max(cumsum(waitingCustomers));departureTimes(next) serverEmptyTime serviceTimes(next);endserverEmptyTime departureTimes(next);unserved(next) 0;end2.Proof. When there are k servers, the relation is given by Dn Sn max{An , min{Dn 1 , Dn 2 , · · · , Dn k }},where D0 D 1 · · · D (k 1) 0. The corresponding Matlab code is given below.function departureTimes ross 1 2(arrivalTimes, serviceTimes, numServers)%ROSS 1 2%%%solves Exerciese Problem 2 of Chapter 1, [1].Reference:[1] Ross: Simulation, Third Edition, Academic Press, 2002.if (numel(arrivalTimes) numel(serviceTimes))error(’Array of arrival times and array of service times must have same size’);endnumCustomers numel(arrivalTimes);serverEmptyTimes zeros(1, numServers); % serverEmptyTimes(i) is the time when% the i-th server is empty.departureTimes zeros(1, numCustomers);for i 1:numCustomers% serverTime is the earliest time when a server is empty; serverNo is% this server’s number (1, 2, ., k).[serverTime, serverNo] min(serverEmptyTimes);if (serverTime arrivalTimes(i))departureTimes(i) arrivalTimes(i) serviceTimes(i);elsedepartureTimes(i) serverTime serviceTimes(i);endserverEmptyTimes(serverNo) departureTimes(i);end5
Chapter 2Elements of Probability1. (a)Proof. B (A Ac ) B AB Ac B. A B A (AB Ac B) (A AB) Ac B A Ac B.(b)Proof. P (A B) P (A Ac B) P (A) P (Ac B) P (A) P (B AB) P (A) P (B) P (AB).2.Proof. A B can be divided into the disjoint union of three sets. The first set consists of all the 6-tupleswhose second entry is 2. This set has 5! 120 elements. This second set consists of all the 6-tuples whosesecond entry is 1. So it has 5! 120 elements. The third set consists all the 6-tuples where 1 occupies eitherthe first entry or the second entry and 2 does not occupy the second entry. It has 2 · 4 · 4! 192 elements.So #AB 432.AB {(1, 2, i, j, k, l), (i, 2, 1, j, k, l) : {i, j, k, l} {3, 4, 5, 6}}. So #AB 2 · 4! 48.ABC {(1, 2, 3, i, j, k) : {i, j, k} {4, 5, 6}}. So #ABC 3! 6.Finally, #A BC #A #BC ABC 3 · 5! 4! 3! 360 24 6 378.3.Proof. By assumption, P (bb) P (bg) P (gb) P (gg) 14 . SoP (gg gg or gb) P (gg)1 .P (gg) P (gb)2Remark: The problem is essentially the same as the coin-flipping problem at the beginning of §2.3.4.Proof. We assume P (bb) P (bg) P (gb) P (gg) 14 . Then the desired probability equals toP (bb bb or bg gb) 1.3Remark: For some subtle issues related to conditional probability, see Feller [2], V.1, Example (c).5.Proof. Since 1 0.5.P4i 1P (X i) (1 2 3 4)c, we conclude c 10. So P (2 X 3) (2 3)/10 6.6
Proof. Since 1 R10f (x)dx cx2 12 0 2c , we conclude c 2. So P (X 21 ) R1122xdx x2 11 34 .27.Proof. Z Z y1{x y} 2e (x 2y) dxdy 2e 2y dye x dx0000Z Z Z 2e 2y (1 e y )dy 2e 2y dy 2e 3y dyZP (X Y )Z0 00211 .338.Proof. E[X] i2i 1 10P4 3.9.Proof. E[X] R102x2 dx 23 .10.Proof. Following the hint, we have E[X] P10i 1E[Xi ]. Note for each i,P (Xi 1) 1 P (type i coupon is not among the N coupons) 1 9N 1 0.9N .10NSo E[X] 10 · (1 0.9N ).11.Proof. P (X i) 16 , i 1, · · · , 6. So E[X] 919126 . Therefore V ar(X) 6 3.5 2.92.16P6i 1i 3.5 and E[X 2 ] 16P6i 1i2 1 6·(6 1)·(2·6 1)6612.Proof. Since 1 R101e 1 .f (x)dx c(e 1), we conclude c Z1E[X] cWe have Zxe dx c xex 10 0and2ZE[X ] c12 xx e dx c1xxe dx c0 x2 ex 10Z 20So V ar(X) E[X 2 ] (EX)2 ce c c2 1 xe dx ce 2E[X] ce c.x01e 1 (e 1 1e 1 ) (e 1)2 1(e 1)2 .13.Proof. V ar(aX b) E(aX b E(aX b))2 E(aX b aEX b)2 a2 E(X EX)2 a2 V ar(X).14.7
Proof. The answer of the problem depends on what distribution the amount of liquid apple follows. Forexample, if we assume it follows a normal distribution, then the problem’s conditions imply mean µ 4 andvariance σ 2 4. Denote by X the amount of liquid apple, then X 4X 4P (X 6) P 1 0.1587, P (3 X 5) P 0.5 0.5 0.3829.2215. 3 2Proof. The probability that a three-engine plane functions is p1 p (1 p) p3 3p2 2p3 . The 2 5 35 4probability that a five-engine plane functions is p2 p (1 p)2 p (1 p) p5 p3 (6p2 15p 10).34So p1 p2 is reduced to 0 (p 1)2 (2p 1), i.e. p 0.5.16.Proof. For i 1, · · · , n, n ip (1 p)n iipP (X i)n i 1 ·. P (X i 1)i1 pni 1n i 1p (1 p)i 1So P (X i) is an increasing function of i if and only if (n i 1)p i(1 p), which is equivalent to(n 1)p i. This shows P (X i) first increases and then decreases, reaching its maximum value when i isthe largest integer less than or equal to (n 1)p.17.Proof. X is the sum of n i.i.d. Bernoulli random variables; Y is the sum of m i.i.d. Bernoulli randomvariables. Independence of X and Y implies these two families of Bernoulli random variables are alsoindependent to each other. So X Y as the sum of n m i.i.d. Bernoulli random variables is binomial withparameters (n m, p).18.Proof. Because Poisson random variables may be used to approximate the distribution of the number ofsuccesses in a large number of trials when each trial has a small probability of being a success. See page18-19 for details.19.Proof. We calculate the moment generating function of X:F (u) E[eXu ] Xk 0eukuuλk λe e λ eλe eλ(e 1) .k!uThen it’s straightforward to calculate F 0 (u) λeλ(e 1) u and F 00 (u) λeλ(eF 0 (0) λ, E[X 2 ] F 00 (0) λ2 λ, and V ar(X) E[X 2 ] (E[X])2 λ.20.8u 1) u(λeu 1). So E[X]
Proof. X can be seen as the limit of a sequence of binomial random variables (Xi ) i 1 , such that Xi hasparameters (ni , pi ) and ni pi λ1 as i .Similarly, Y can be seen as the limit of a sequence of binomial random variables (Yi ) i 1 , such that Yihas parameters (mi , pi ) and mi pi λ2 as i .By the result of Exercise 17, Xi Yi is binomial with parameters (mi ni , pi ) such that (mi ni )pi (λ1 λ2 ). Therefore, X Y limi (Xi Yi ) is Poisson with parameter λ1 λ2 .For an analytic proof, we noteP (X Y k) kXP (X i)P (Y k i)i 0 kXe λ1i 0λi1 λ2 λk i2·ei!(k i)! ke (λ1 λ2 ) Xk!λi1 λk i2k!i!(k i)!i 0 e (λ1 λ2 )(λ1 λ2 )k .k!21.Proof. We can utilize this recursion equations as follows:function p ross 2 21(lambda, n)%ROSS 2 21%%%%%solves Exerciese Problem 21 of Chapter 2, [1]. The functioncalculates the probability of a Poisson random variable withrate LAMBDA being equal to N.Reference:[1] Ross: Simulation, Third Edition, Academic Press, 2002.if (lambda 0) (n 0)error(’Invalid argument’);endp exp(-lambda);if (n 0)return;elsefor i 0:(n-1)p p * lambda / (i 1);endend22.Proof. P (X n) P k n 1p(1 p)k 1 p(1 p)nP k 0 (123.9 p)k p(1 p)n ·1p (1 p)n .
Proof. Let (Xi ) i 1 be i.i.d. Bernoulli random variables with parameter p 0.6, such that(1 if A wins the i-th matchXi 0 otherwise.PnIf we define Sn i 1 Xi , then A wins the match if and only if the random walk Sn reaches 5 before ( 5)it reaches -5. This probability is 5 ( 5) 0.5 by Wald’s equation. For details, see Durrett [1], page 180,1Example 1.5.24.PnProof. X i 1 Yi is self-evident. By symmetry, Yi has the same distribution, with P (Yi 1) So E[X] NnN M .NN M .25.Proof. P (5 U 15) 15 530 13 .26.Proof. The moment generating function isZ Z (x µ)2(x µ uσ)2 u2 σ 4 2µuσ 21 2 211 2σ2uXux2σ 2 edx e dx e 2 u σ µu .F (u) E[e ] e 2πσ2πσ So E[X] F 0 (u) u 0 µ, E[X 2 ] F 00 (u) u 0 σ 2 µ2 , and V ar(X) E[X 2 ] (E[X])2 σ 2 .27.PnProof. If X is a binomial random variable with parameters (n, p), X can be written as X i 1 Xi , where(Xi )ni 1 is a sequence of i.i.d. Bernoulli random variables with parameters p. So by central limit theorem(note E[Xi ] p, V ar(Xi ) p(1 p)),PnXii 1 pX npp n pn N (0, 1), as n .np(1 p)p(1 p) Rx2X npThis is the rationale that P x 12π e x /2 dx when n is large.np(1 p)Remark: This provides an approximate way to compute binomial distributions while avoiding calculationof factorials. Moreover, since Poisson distribution can be approximated by binomial distribution, this exerciseproblem shows that, when λ is large, Poisson distribution can be approximated by N (λ, λ). See Feller [2],VII.5 for details.28.Proof. The Laplace transform is (u 0)F (u) E[e uXZ ] e ux λe λx dx Xλu n ,λ u n 1λfor u sufficiently small. So E[X] F 0 (u) u 0 λ1 , E[X 2 ] F 00 (u) u 0 1λ2 .2λ2 ,and V ar(X) 2λ2 1 2λ 29.1 I didn’t find a simple, elementary solution, except by calculating one-by-one the probability that A wins the match at then-th individual game (n 5, 6, 7, 8, 9).10
Proof.12.We first give a proof without computation. By symmetry,P (C is the last to leave) 2P (A leaves before B and B leaves before C) 2P (B leaves before C A leaves before B)P (A leaves before B).Since exponential random variables are memoryless, after A leaves before B, C and B will start anew, asif they started being served simultaneously. So P (B leaves before C A leaves before B) 21 and we canconclude P (C is the last to leave) 2 · 12 · 21 12 .A direct computation is carried out as follows. Denote the service times of A, B and C by X, Y and Z,respectively, we haveP (C is the last to leave)1 P (X Y Z) P (Y X Z)Z λt 1 2P (X t Y Z t)λe λt dt1!Z0 λte λt λe λt dt 1 21!01 1 2·41 .2 30.Proof. We note for any t 0,P (max(X, Y ) t) P (X t and Y t) P (X t)P (Y t) (1 e λt )(1 e µt ) 1 e λt e µt e (λ µ)t .So max(X, Y ) is not an exponential random variable.31.Proof. The probability is equal to P (Nt 0) e λt e 0.3·4 0.3012.32.Proof.P (N (s) k N (t) n) P (N (s) k, N (t) n)P (N (s) k, N (t) N (s) n k) P (N (t) n)P (N (t) n) P (N (s) k)P (N (t s) n k) P (N (t) n) (λs)k λsk! e(λ(t s))n k λ(t s)e(n k)!n(λt) λtn! e·sk (t s)n kn!·tnk!(n k)! s ks n kn1 .kttRemark: This gives an interesting observation: when N (t) is known, the number of events by time s(s t) follows a binomial distribution with parameters (N (t), s/t). Equivalently, we can say given N (t) n,the timings of the first n events are i.i.d. uniformly distributed over (0, t).33.11
Proof.P (N (s) k N (t) n) P (N (s) N (t) k n N (t) n) P (N (s t) k n) (λ(s t))k n λ(s t)e.(k n)!Remark: Intuitively, the formula should be clear: given N (t) n, the conditional distribution of N (s)(s t) behaves l
This is a solution manual for the textbook Simulation, 3rd Edition, by Sheldon M. Ross (2002, Academic Press). This version omits the Problem 8, 9, 18 of Chapter
