Homework 2 AnswersMATH 56A: STOCHASTIC PROCESSESANSWERS TO HOMEWORKHomework 2 Answers1) The first problem is the queueing problem.a) When is this positive recurrent?We need to find the invariant distribution π. This is the solution ofπ(n) =Xmπ(m)p(m, n)andXπ(n) = 1.For n > 0, the first equation gives:π(n) = p(1 − q)π(n − 1) + (qp + (1 − p)(1 − q))π(n) + q(1 − p)π(n + 1)Here it helps to use some notation:a = p(1 − q), b = q(1 − p), c = qp + (1 − p)(1 − q)These numbers add up to 1 since they are the numbers in the nth row of the transitionmatrix.a + b + c = 1.So,π(n) = aπ(n − 1) + cπ(n) + bπ(n + 1)(1 − c)π(n) = (a + b)π(n) = aπ(n − 1) + bπ(n + 1)π(n) =aa + bπ(n − 1) +ba + bπ(n + 1)To solve this you putπ(n) = rnThenr =aa + b+ba + br2So, either r = 1 orr = a/b =p(1 − q)q(1 − p)An invariant distribution exists if and only if r < 1 which is equivalent to p < q. In thatcase, the invariant distribution is:π(n) = Cabnfor n > 0andπ(0) = C(1 − q)1This last equation comes from:π(0) = π(0)p(0, 0) + π(1)p(1, 0) = (1 − p)π(0) + bπ(1)pπ(0) = bπ(1) = bC(a/b) = aC = p(1 − q)C.π(0) = (1 − q)C.To find C, we take the sum:Xπ(n) = C1 − q + (a/b) + (a/b)2+ · · ·= C11 − a/b− q1 = Cbb − a−q(q − p)q − p= Cq − q2q − pC =q − pq − q2This makesπ(0) = (1 − q)C =q − pq= 1 − p/q.And, for n > 0 we have:π(n) = C(a/b)n=(q − p)pn(1 − q)n(q − q2)qn(1 − p)n=(q − p)pn(1 − q)n−1qn+1(1 − p)nb) When is this chain transient?Now we have to find a function α(n) so that α(0) = 0,α(n) =Xp(n, m)α(m)andinfα(n) = 0.This gives:α(n) = p(n, n − 1)α(n − 1) + p(n, n)α(n) + p(n, n + 1)α(n + 1)α(n) = bα(n − 1) + cα(n) + aα(n + 1)(1 − c)α(n) = (a + b)α(n) = bα(n − 1) + aα(n + 1)This is the same equation as for π(n) except that a, b are switched. Thus, the chain istransient iff b < a iff q < p. The value of the function α(n) for all n isα(n) = C(b/a)nThe constant C must be equal to 1 to make this agree with α(0) = 1. So,α(n) =qn(1 − p)npn(1 − p)nc) In the remaining case, p = q, the chain must be null-recurrent.2) The second problem is easy.a) When is this chain positive recurrent?As I explained in class, the chain is positive recurrent if and only if the expected returntime (to any state) is finite. Take the state 0. Then, you go to state x with probability pxand then return to 0 in x more steps. So, the expected value of the return time T isE(T ) =∞Xn=1(n + 1)pn.SincePpn= 1 this isE(T ) = 1 +∞Xn=1npn.So, the chain is positive recurrent if and only if∞Xn=1npn< ∞.b) Find the invariant distribution.LetL =∞Xn=1npn< ∞.Then,π(0) =1E(T )=1L + 1.What about π(n) for n > 0?The equation isπ(y) =Xπ(x)p(x, y)π(y) = π(0)p(0, y) + π(y + 1)p(y + 1, y) = π(0)py+ π(y + 1)∆n= π(n + 1) − π(n) = −π(0)pn= −pn1 + L∆n−1= π(n) − π(n − 1) = −π(0)pn−1= −pn−11 + LAdding these up (and using p0= 0) we get:π(n + 1) − π(0) = −p1+ p2+ · · · + pn1 + Lπ(n + 1) = π(0) −p1+ p2+ · · · + pn1 + L=1 − p1− p2− · · · − pn1 + Lπ(n) =1 − p1− p2− · · · − pn−11 + LMost students divided by the sum instead of using the value of π(0). This gives a messy butcorrect answer.2.14. a) Explain why φ0(a) < 1.This is obvious from the graph. The rigorous proof is by the mean value theorem. Sinceφ(a) = a and φ(1) = 1, there is a number b between a and 1 so that φ0(b) = 1. Sinceφ00(x) > 0 for all x this implies that φ0(x) < 1 for all x < b in particular f0(a) < 1.b) Show that, for n sufficiently largea − an+1≤ ρ(a − an)for some ρ < 1.The answer is: ρ = φ0(a) < 1. Since φ(x) is concave up and φ(an) = an+1, the point(an, an+1) lies on the graph of φ which lies above the tangent line to φ at the point (a, a)which is given by the equation:y − a = ρ(x − a)Putting in x = anwe get that the point (an, a + ρ(an− a)) is on the tangent line. So,an+1≥ a + ρ(an− a)Subtract a from both sides to get:an+1− a ≥ ρ(an− a)Change sign to get:a − an+1≤ ρ(a − an)c) Show that, for some b > 0, c < ∞,P(extinction | Xn6= 0) ≤ ce−bnThe answer is that b = − ln ρ, i.e.,ρ = e−bSince ρ < 1, b > 0. Also,c =11 − aHere is the proof: The conditional probability is:P(extinction | Xn6= 0) =P(extinction and Xn6= 0)P(Xn6= 0)=a − an1 − an.First the denominator:an< a1 − an> 1 − a11 − an<11 − a= cNext, the numerator:a − an≤ ρnThis is by induction on n. For n = 0 we have:a − a0= a < 1 = ρ0.Suppose that the statement is true for n. Thena − an+1≤ ρ(a − an) ≤ ρρn= ρn+1So, the statement holds for all n. So,P(extinction | Xn6= 0) =a − an1 − an≤ρn1 − a= cρn= ce−bn.2.16. a) Show that, for n > 0,π(n) =Xm=n−1π(m)pn−mThe definition of invariant distribution gives:π(n) =Xπ(m)p(m, n) =Xπ(m)pn−mthe only question is: Over what value of m is this sum taken? But that is easy since pxisonly defined for x ≤ 1. So we must haven − m ≤ 1n − 1 ≤ m.b) Let qk= p1−k. Then show that there is some α ∈ (0, 1) so thatα = φ(α) = q0+ q1α + q2α2+ · · ·The number α is the extinction probability. It will be less than 1 if the average numberof children is greater than 1. Call this number µ∗since there is already a µ in the problemgiven byµ =Xnpn< 0.The average number of offspring isµ∗=Xkqk=Xkp1−kButPp1−k= 1. So,1 − µ∗=X(p1−k− kp1−k) =X(1 − k)p1−k= µ.So,µ∗= 1 − µ > 1.c) Use the α from part (b) to find the invariant distribution.Start withα =∞Xk=0qkαk=∞Xk=0p1−kαk=∞Xm=n−1pn−mα1−n+mNow multiply both sides by αn−1to get:αn=∞Xm=n−1pn−mαmThis implies thatπ(n) = Cαnfor n > 0. To find C we add this up:C =1Pαn= 1 − αSo,π(n) = (1 − α)αnThis is a probability distribution. After one generation we get a new probability distributionπP = (?, π(1), π(2), · · · )The first coordinate must be π(0) since the numbers add up to 1. So, this is the invariantprobability