1.  Consider the Markov chain on I = {0, 1, 2, . . . , N} with the following transition matrix:

p(0, 1) = 1 ,

p(i, i + 1) = 1/2 ,

p(N, N - 1) = 1 , p(i, i - 1) = 1/2

for 1 s i s N - 1 .

All other entries of p are zero.

(a)  (3 points) Find the stationary distribution π .

(b)  (2 points) If I start the chain at X0  = 0, what is the expected return time?  That is, what is E0T0 ?

2.   (a)  (3 points) In class, we proved that if we have a Markov chain on a finite state space I, we can decompose I as a disjoint union

I = T u R1 u . . . u Rk  ,

where T is a set of transient states and each Rj  is a closed irreducible set of recurrent states.

Find these sets explicitly for the Markov chain on I = {1, 2, 3, . . . , 7} with

1     2     3     4     5     6     7

(b)  (3 points) Find limn→o pn (5, 1).

3. I have two umbrellas, some at my office and some at home.  Every day I walk to the office in the morning and back home in the evening (a total of two trips per day); if it is raining, I will take an umbrella if one is there.  Otherwise, I get wet.  Assume that independently of the past, it rains on each trip with probability 1/3.  Let Xn  be the number of umbrellas at my current location after the nth trip; then Xn  is a Markov chain.

(a)  (2 points) Find the transition probability matrix for this Markov chain.

(b)  (4 points) What is the limiting fraction of the time I get wet?

4.  Suppose we have an irreducible Markov chain Xn  on I = {1, 2, . . . , N} (where N > 1)

with transition probability matrix p. Let S0  = 0 and for each k > 0, let Sk+1  = inf{n > Sk  : Xn   XSk} .

For each m > 0, define Zm  = XSm   .

(a)  (3 points)  Show that Zm  is also a Markov chain — you don’t have to write a huge amount, but please make the argument / steps clear.