4. Homework 4 (Chap 2)2.7. 2.8. 2.18.MATH 56A: FALL 2006HOMEWORK AND ANSWERSMath 56a: Homework 44. Homework 4 (Chap 2)p. 59 #2.7, 8, 182.7. Are these positive recurrent, null recurrent or transient?(a) This process is null recurrent:p(x, 0) =1x + 2, p(x, x + 1) =x + 1x + 2In this process, you keep coming back to state 0. However, to be recurrent you need to knowthat the probability of returning to 0 is 1. The probability that you will get to state n isp(0, 1)p(1, 2) ···p(n − 1, n) =122334···nn + 1=1n + 1Since this goes to 0, the probability of returning to 0 is 1. So, this is recurrent.To see if it is positive recurrent you need to find an invariant distribution or show thatone exists. This is a vector solution of the matrix equationπP = πso that the entries of π add to 1. But the matrix equation gives:π(x + 1) = π(x)p(x, x + 1) =π(x)(x + 1)x + 2So, π(x)(x + 1) = C is constant. But this is impossible since1 =Xπ(x) =XCx + 1is a diverging sum. So, there is no invariant distribution. So, this process is null recurrent.(b) This one is positive recurrent:p(x, 0) =x + 1x + 2, p(x, x + 1) =1x + 2This one has a higher probability of returning to 0 than the last one. So, it must also berecurrent. To see if is it positive recurrent we again look for an invariant distribution:π(x + 1) = π(x)p(x, x + 1) =π(x)x + 24HW AND ANSWERS 2006 5π(x) =π(0)(x + 1)!The equationPπ(x) = 1 givesπ(0) =X1(x + 1)!−1= (e − 1)−1So,π(x) =(e − 1)−1(x + 1)!is an invariant distribution and the process is p ositive recurrent.(c) This one is transient:p(x, 0) =1x2+ 2, p(x, x + 1) =x2+ 1x2+ 2Since the return to 0 probabilities converge the process is transient:∞Xx=11x2+ 2<X1x2=π26< ∞(Or use the integral test or the p-test for convergence.) To see that the process is transient,take a number n so that∞Xx=n1x2+ 2< Then, once you reach state x, the probability that you will ever return to 0 is less than .Since there is only one communication class, you keep returning to x or higher and eventuallyyou never return to 0.2.8. Branching process.(a) p0= .25, p1= .4, p2= .35The extinction probability is the smallest positive solution ofa = φ(a) =Xpiai= .25 + .4a + .35a2So,a =.6 ±√.36 − .35.7= 1,57The smaller number is the answer: a = 5/7.(b) p0= .5, p1= .1, p3= .4Here you get the cubic equation.4a3− .9a + .5 = 06 HW AND ANSWERS 2006But you can factor out a − 1 since a = 1 is always a solution. You get4a2+ 4a − 5 = 0a =√6 − 12≈ .7247(c) p0= .91, p1= .05, p2= .01, p3= .01, p6= .01, p13= .01Here the average number of offspring isXipi= .29 < 1Therefore, the probability of extinction is one.(d) pi= (1 − q)qifor some 0 < q < 1.This time, the average number of offspring isµ =Xipi= (1 − q)Xiqi=q1 − qThis is ≤ 1 if q ≤ 1/2. So a = 1 in that case.HW AND ANSWERS 2006 7If q > 1/2 then the extinction probability is the solution ofa =X(1 − q)qiai=1 − q1 − qawhich givesa =1 − qq2.18. This is a rigorous proof of Stirling’s formulan! ∼√2πnn+1/2e−n(a)limn→∞Xn≤k<n+a√np(n, k) =Za01√2πe−x2/2dxThe central limit theorem says:Theorem 2.1. If Yn= X1+ X2+ ··· + Xnis the sum of i.i.d random variables with meanµ and standard deviation σ then the random variableYn− nµσ√napproaches a standard normal distribution in the sense thatlimn→∞P(nµ + bσ√n ≤ Yn< nµ + aσ√n) =Zab1√2πe−x2/2dxFor the Poisson distribution we have µ = 1 = σ. If we take b = 0 then the limit becomes:limn→∞P(n ≤ Yn< n + a√n) = limn→∞Xn≤k<n+a√np(n, k)(b) We need to show that, for n ≤ k < n + a√n,e−a2p(n, n) ≤ p(n, k) ≤ p(n, n)Let δ = k − n. Thennkk!=nnn!·nn + 1·nn + 2···nn + δ≥nnn!nδ(n + δ)δBut,nδ(n + δ)δ=1(1 + δ/n)δ≥ e−δ2/nsince 1 + δ/n ≤ eδ/nande−δ2/n> e−a28 HW AND ANSWERS 2006since δ2< a2n. This shows thatp(n, k) = e−nnkk!≥ e−nnnn!e−a2≥ e−a2p(n, n).The other inequality is easy.(c) Finally we are supposed to conclude thatp(n, n) ∼1√2πnfrom which Stirling’s formula follows.From (a) and (b) we geta√ne−a2p(n, n) − ≤Za01√2πe−x2/2dx ≤ a√np(n, n) + where > 0 is arbitrarily small. (This comes from replacing only the middle terms with itslimit: If an< bnthen lim an≤ lim bnbut lim an≤ bn+ .)Divide by a and take limit as a → 0 gives√np(n, n) − ≤1√2π≤√np(n, n) + which is what we wanted to
View Full Document
Unlocking...