Let Xn be a Markov chain with state space {0, 1, ..., N} with

N 2 and suppose that Xn is a martingale. Let Vk = min{n 0 :

Xn = k}, k = 0, 1, ..., N, and

= min(V0, VN ).

Suppose that Pk( < ) > 0 for all k = 1, 2, ..., N 1. Prove that

Pk( < ) = 1 and Pk(VN < V0) = k/N for all k = 0, 1, ..., N. (Hint:

Show first that there are n 1 and < 1 such that for all x = 1, ..., N

we have Px( n) . Four points for that.)