Statistics 251b/551b, spring 2009Take-home test 1Due: Wednesday 4 March• You should prepare solutions to the following questions without help orhints from anybody else. In particular, if you have been working in a groupyou must suspend the group arrangement for the test; you must not discussthe questions with your group buddy.• If you have questions of interpretation, or of clarification of the meaningof a question, ask David Pollard.• Make sure you explain your calculations and notation.• Each part of each question is worth 5 points.• As usual, even if you are unable to solve one part of a question you maystill use the result for the following parts.[1] For each of the following questions, S denotes the set {0, 1, 2, 3, . . . } = {0} ∪ N.(i) Give an example of an irreducible Markov chain with state space S for which thereexists a stationary measure but no stationary probability distibution.(ii) Give an example of a Markov chain with state space S that has at least two distinctstationary probability distibutions.(iii) Give an example of a martingale taking values in S that is not a Markov chain.(iv) Give an example of an irreducible, aperiodic Markov chain with state space S forwhich Pi{Xn= i} = 0 for 1 ≤ n ≤ 100 for every state i.[2] For a fixed positive integer d letS = {(i1, i2) ∈ N × N : 1 ≤ i1≤ d and 1 ≤ i2≤ d}denote the d × d lattice of points with integer coordinates running from 1 to d.Let Xn= (Xn,1, Xn,2) be a random walk on S: if Xn= x /∈ {(1, 1), (d, d)} thenXn+1has the equal probability of being at one of the neighbors of x. Make both(1, 1) and (d, d) absorbing states. For example, if x = (x1, x2) with 0 < xi< dfor i = 1, 2 then P (x, y) = 1/4 for each y in the set{(x1, x2+ 1), (x1, x2− 1), (x1+ 1, x2), (x1− 1, x2)}For x on the edges of the lattice, there are fewer neighbors and the transitionprobabilities will be slightly different.Define τ = inf{n ∈ N : Xn= (1, 1) or Xn= (d, d)}.Define B = {τ < ∞, Xτ= (d, d)}.Define Zn= Xn,1+ Xn,2for each n.(i) Write down the transition probabilities P (x, y) when x is on the edge of the lattice.(That is, at least one of x1and x2is equal to 1 or d.)(ii) Define f(x) = x1+ x2for x = (x1, x2) ∈ S. Show that f is harmonic. That is,show that E (f(X1) | X0= x) = f(x) for each x.(iii) Explain why Px{τ < ∞} = 1 for every x in S.(iv) Show that Znis a martingale for each initial state x of the Xn-chain.(v) Show that Znis also a Markov chain. Write down the state space and transitionprobabilities for the Zn-chain.(vi) Define g(x) = PxB. Show that g is a harmonic function.(vii) Find g(x) for each x in S.[3] Question 1 on Homework 3 described a modification of the queueing examplefrom Section 2.3 of the Chang notes. I got myself greatly confused over the prob-lem of independence of Xnand D1, D2,. . . , Dn. The following questions revisitthe modified problem, with the aim of proving thatPπ{X2= k, D1= δ1, D2= δ2} = πkθ(δ1)θ(δ2) for all δi∈ {0, 1}, all k ≥ 0,<1>where θ(1) = p and θ(0) = 1−p. That is, the aim is to prove independence of X2,D1, and D2. To this end defineG(k, δ1, α1, δ2, α2) = Pπ{X2= k, D1= δ1, A1= α1, D2= δ2, A2= α2}.and let j = k − α2+ δ2and i = j − α1+ δ1. Note that δ1and α1are uniquelydetermined by i and j if |i − j| = 1; and δ2and α2are uniquely determined by jand k if |j − k| = 1You may assume that the chain has stationary distribution π and transitionprobabilities as shown on the Solutions to Sheet 3.(i) For each i ≥ 0 define fi(δ) = Pi{A1= D1= δ} for δ ∈ {0, 1} and i =0, 1, 2, . . . . Write down the expression for fi(δ). Hint: You will need to distin-guish between the cases i = 0 and i ≥ 1.(ii) Explain whyG(k,δ1, α1, δ2, α2)= Pπ{X0= i, X1= j, X2= k, D1= δ1, A1= α1, D2= δ2, A2= α2}for all k ≥ 1 and all δi, αi∈ {0, 1}.(iii) If α16= δ1and α26= δ2show thatG(k,δ1, α1, δ2, α2)= Pπ{X0= k, X1= j, X2= i}= Pπ{X0= k, D1= α2, A1= δ2, D2= α1, A2= δ1}.(iv) If α1= δ1and α26= δ2show thatG(k,δ1, α1, δ2, α2)= Pπ{X2= k, X1= j, X0= j, D1= δ1= A1}= πjfj(δ1)P (j, k)= Pπ{X0= k, D1= α2, A1= δ2, D2= α1, A2= δ1}.(v) Similarly, if α16= δ1and α2= δ2, show thatG(k,δ1, α1, δ2, α2)= Pπ{X0= k, D1= α2, A1= δ2, D2= α1, A2= δ1}.(vi) If α1= δ1and α2= δ2, show thatG(k,δ1, α1, δ2, α2)= Pπ{X2= k, X1= k, X0= k, D1= δ1= A1, D2= δ2= A2}= πkfk(δ1)fk(δ2)= Pπ{X0= k, D1= α2, A1= δ2, D2= α1, A2= δ1}.(vii) Complete the proof of <1>.Bonus points if you find and correct any errors in this