6.262 Discrete Stochastic Processes, Problem Set 3 Solutions

Solutions to Homework 3 6.262 Discrete Stochastic Processes MIT, Spring 2011 Solution to Exercise 2.3: a) Given Sn = τ , we see that N (t) = n, for τ ≤ t only if there are no arrivals from τ to t. Thus, Pr (N (t) = n|Sn = τ ) = exp (−λ(t − τ )) b) � t Pr (N (t) = n) = Pr (N (t) = n)|Sn = τ )fSn (τ )dτ τ =0 � t = e−λ(t−τ ) τ =0 t λn τ n−1 e−λτ dτ (n − 1)! λn τ n−1 e−λt dτ (n − 1)! τ =0 � t λn e−λt = τ n−1 dτ (n − 1)! τ =0 � = = (λt)n e−λt n! Solution to Exercise 2.5: a) The 3-tuples 000 and 111 have probabiity 1/8 as the unique tuples for which N (3) = 0 and N (3) = 3 respectively. In the same way, N (2) = 0 only for (Y1 , Y2 ) = (0, 0), so (0,0) has probability 1/4. Since (0, 0, 0) has probability 1/8, it follows that (0, 0, 1) has probability 1/8. In the same way, looking at N (2) = 2, we see that (1, 1, 0) has probability 1/8. The four remaining 3-tuples are illustrated below, with the constraints imposed by N (1) and N (2) on the left and those imposed by N (3) on the right. 1/4 1/4 0 0 1 1 1 1 0 0 0 1 0 1 1/4 �� 1/4 It can be seen by inspection from the figure that if (0, 1, 0) and (1, 0, 1) each have probability 1/4, then the constraints are satisfied. There is one other solution, which is to choose (0, 1, 1) and (1, 0, 0) to each have probability 1/4. 1 b) Arguing as in part a), we see that Pr (0, 0, 0) = (1 − q)3 , Pr (0, 0, 1) = (1 − q)2 p, Pr (1, 1, 1) = q 3 , and Pr (1, 1, 0) = q 2 (1 − q). The remaining four 3-tuples are constrained as shown below. q(1 − q) q(1 − q) 0 0 1 1 1 1 0 0 0 1 0 1 2q(1 − q)2 �� 2q 2 (1 − q) If we set Pr (0, 1, 1) = 0, then Pr 0, 1, 0) = q(1 − q), Pr (1, 0, 1) = 2q 2 (1 − q), and Pr (1, 0, 0) = q(1 − q) − 2q 2 (1 − q) = q(1 − q)(1 − 2q). This satisfies all the binomial con­ straints. � � � c) We know that τk=0 τk pk q τ −k = 1. This says that the sum of all 2t vectors is 1. This constraint can then replace any of the others for that τ . d) We have the constraint that the sum of the vectors is 1, and τ remaining constraints �t for each τ . Since τ =1 τ = (t + 1)t/2, at most (t + 1)t/2 + 1 constraints are linearly independent, so that the dimensionality of the 2t vectors satisfying these linear constraints is at least 2t − (t + 1)t/2 − 1. Solution to Exercise 2.10: a) N (t + s) = N (t) + Ñ (t, s), where N (t) and Ñ (t, s) are independent. Thus, for m ≥ n, ˜ (t, s) = m − n) PN (t),N (t+s) (n, m) = Pr(N (t) = n) Pr (N = Pr (N (t) = n) Pr (N (t − s) = m − n) = (λt)n e−λt (λs)n−m e−λs n! (n − m)! Where the second equation is because of the stationary increment property of Poisson process. b) E[N (t)N (t + s)] = E[N (t){N (t) + Ñ (t, t + s)}] = E[N 2 (t)] + E[N (t)Ñ (t, t + s)] = E[N 2 (t)] + E[N (t)]E[N (s)] Where the last equation is because of the independent increment property of Poisson process. 2 E[N (t)] = ∞ � n(λt)n e−λt n=1 2 E[N (t)] = = n! = λt ∞ � (λt)n−1 e−λt n=1 (n − 1)! = λt ∞ � n2 (λt)n e−λt n=1 ∞ � n=1 n! ∞ n(λt)n e−λt � n(n − 1)(λt)n e−λt + n! n! = λt + (λt)2 n=1 ∞ � (λt)n−2 e−λt n=2 (n − 2)! = λt + (λt)2 Thus, E[N (t)N (t + s)] = λt + (λt)2 + (λt)(λs) c) ˜ (t2 , t4 )] E[Ñ (t1 , t3 )Ñ (t2 , t4 )] = E[{Ñ (t1 , t2 ) + Ñ (t2 , t3 )}N ˜ (t3 , t4 )] ˜ (t2 , t4 )] + E[Ñ 2 (t2 , t3 )] + E[Ñ (t2 , t3 )N = E[Ñ (t1 , t2 )N ˜ (t2 , t3 )]E[N ˜ (t3 , t4 )] = E[Ñ (t1 , t2 )]E[Ñ (t2 , t4 )] + E[Ñ 2 (t2 , t3 )] + E[N = λ2 (t2 − t1 )(t4 − t2 ) + λ2 (t3 − t2 )2 + λ(t3 − t2 ) + λ2 (t3 − t2 )(t4 − t3 ) = λ2 (t3 − t1 )(t4 − t2 ) + λ(t3 − t2 ). Solution to Exercise 2.11: a) We can visualize the set of experiments as corresponding to the splitting of a Poisson process {N (t); t ≥ 0}. That is, the arrivals in the Poisson process are split into K different Poisson processes, with an arrival going into sub-process k with probability pk . An arrival that goes into the k-th subprocess is identified as an outcome ak . Visualize the overall process as having rate λ, and visualize the set of experiments as lasting for one unit of time. Since λpi is the rate of the i-th subprocess, Ni , the number of experiments resulting in outcome ai over the given unit of time, is a Poisson random variable of mean λpi , Pr(Ni = n) = (λpi )n e−λpi ,n ≥ 0 n! b) Since the subprocesses are independent, N1 and N2 are independent random variables. The sum of independent Poisson random variables is Poisson, so 3 Pr(N1 + N2 = n) = [λ(p1 + p2 )]n e−λ(p1 +p2 ) ,n ≥ 0 n! c) Viewing {N (t); t ≥ 0} as being split into subprocess 1 or no subprocess 1, we use (2.25) to get � � n n1 p (1 − p1 )n−n1 , 0 ≤ n1 ≤ n Pr(N1 = n1 |N = n) = n1 1 d) This is the same as part c), except the subprocess of interest is the combination of subprocesses 1 and 2. The success rate is λ(p1 + p2 ), so � � n (p1 + p2 )m (1 − p1 − p2 )n−m , 0 ≤ m ≤ n Pr(N1 + N2 = m|N = n) = m e) The toal number of arrivals over one unit of time, N , is the sum of the arrivals for subprocess 1 and for the other subprocesses, and these are independent. Thus, given N1 = n1 , N = n1 + N1c where N1c is the number of arrivals for the other processes (which collectively have rate λ(1 − p1 )) over one unit of time. Hence, [λ(1 − p1 )]n−n1 e−λ(1−p1 ) , n ≥ n1 (n − n1 )! Alternatively, parts (a) and (c) can be used in Bayes’ rule with some algebra to arrive at the same result. Pr(N = n|N1 = n1 ) = Solution to Exercise 2.12: a) Passenger arrivals and bus arrivals are independent Poisson processes, so we can visualize them as a splitting of a joint arrival process of rate λ + µ (i.e., the rate at which buses and customers combined arrive). Each joint arrival is independently a customer with probability µ/(λ + µ). Thus, starting either at time 0 or immediately after a bus arrival, the probability of exactly n customers followed by a bus is [µ/(λ + µ)]n [λ/(λ + µ)]. Letting Nm be the number of customers entering the m-th bus, m ≥ 1, PNm (n) = [µ/(λ + µ)]n [λ/(λ + µ)] b) Let Xm be the m-th bus interarrival interval (i.e., the interval between the m − 1-th and m-th bus), and let Sm be the arrival epoch of the m-th bus. Since bus arrivals and customer arrivals are independent, Pr(Nm = n|Sm−1 = s, Xm = x) is the unconditional probability of n customers arriving between s and s + x, i.e., (µx)n e−µx /n!. Since this is independent of Sm−1 , 4 Pr(Nm = n|Xm = x) = (µx)n e−µx /n! c) Using the same argument as in part (a), which applies to starting at time 0, time 10 : 30, or any other time, the probability that n customers enter the next bus is [µ/(λ + µ)]n [λ/(λ + µ)]. d) From part (b), the PMF of the number of customers who arrive from 10 : 30 to 11 is given by (µ/2)n e−µ/2 /n! (assuming µ is arrivals per hour). The PMF of the number of passengers who arrive between 11 and the next bus arrival is [µ/(λ + µ)]n [λ/(λ + µ)]. The PMF of the total number of customers N entering the next bus is then given by the convolution of these two PMFs since the two numbers are independent. Pr(N = n) = n � � m=0 µ λ+µ �m λ (µ/2)n−m e−µ/2 λ+µ (n − m)! e)Moving backward in time, each arrival to the combined process is a customer with probability µ/(λ + µ). Thus, letting Npast be the number of customers since the last bus, we see that Npast has the same geometric distribution as we found in part (a). PNpast (n) = [µ/(λ + µ)]n [λ/(λ + µ)] f ) In part (e), we found the PMF for the number of customers Npast waiting at 2 : 30. In part (c), we found the PMF for future customers Nfuture arriving before the next bus. These two random variables are independent, and thus the PMF for the total number Ntot of customers Npast + Nfuture entering the next bus is: Pr(Ntot = n) = n � � m=0 µ λ+µ �m λ λ+µ � µ λ+µ �n−m λ = (n + 1) λ+µ � µ λ+µ �n � λ λ+µ �2 This is an example of the ”paradox of residual life” which is explored in detail in chapter 4. When we look at a sample function of Poisson bus arrivals, any given time such as 2 : 30 is more likely to lie in a large interval than a small interval, which is why the interval from past bus to future bus is larger (on the average) than the expected inter-arrival interval. g) Given that I arrive at 2 : 30 to wait for a bus, the grand total NGT of customers to enter the bus is 1 + Npast + Nfuture , and from the solution to (f), we get � Pr(NGT = n) = Pr(Ntota = n − 1) = n 5 µ λ+µ �n−1 � λ λ+µ �2 Do not get discouraged if you did many parts of this problem incorrectly. You will soon have a number of alternative insights about problems of this type, and they will almost start to look straightforward. Solution to Exercise 2.23: Here, we have arrivals from process N2 with rate γ switching on (and off) the arrivals from the process N1 with rate λ, to create the switched process NA . Note that N1 and N2 are independent, so we will be using the combined/split processes framework whenever convenient. a) We are interested in the number of arrivals of the first process during the n-th period the switch is on. Starting at time t (whatever it may be) when the n-th ”on” period begins and continuing until the next arrival of the second process when the ”on” period ends, we have that the first process will register k arrivals if and only if out of the first k + 1 arrivals of the combined process, the first k came from the first process. Thus, letting Mn denote the number of arrivals of the first process during the n-th period the switch is on, we have, � pMn (k) = λ λ+γ �k � γ λ+γ � , for k ∈ Z+ b) Now we are interested in the number of arrivals of the first process between time zero and the first arrival of the second process, give that the first arrival of the second process occurs at time τ . Since the two processes are independent,this is just the number of arrivals of the first process in the interval [0, τ ]. Thus, the PMF of interest is given by, pN1 (τ ) (n) = (λτ )n e−λτ , for n ∈ Z+ n! c) Let E be the event that n arrivals of the first process occur before the first arrival of the second process. Given that E occurred, we are interested in the corresponding arrival epoch S1 of the second process. Consider the first n + 1 arrivals of the combined process and note that arrivals are switched either to the first process or the second process independently. Here, it happens that the first n arrivals were switched to the first process, while (n + 1)-st arrival was switched to the second process. It follows that S1 is simply the (n + 1)-st epoch of the combined process. But, regardless of the switching pattern, the probability density corresponding to the (n + 1)-st epoch of the switch process is given bu the Erlang density of order n + 1 and rate λ + γ. The desired result thus becomes, fS1 |E (s) = (λ + γ)n+1 sn e−(λ+γ)s , for s ≥ 0 n! 6