Q 3 Let Xn be a Markov chain on 0 1 m with transition ma

Q 3 Let Xn be a Markov chain on {0, 1 . . . , m} with transition matrix Pi,i+1 = 1 - i/m, Pi,i-1 = i/m, Show by induction (or otherwise) that E[Xn - m/2|X0 = i] = (i - m/2)(1 - 2/m)^n.

Solution

Given that

Pi,i+1 = 1 - i/m, Pi,i-1 = i/m

Consider xn-m/2 when n =1

E(x1-m/2/x0 =i) = (i-m/2) (1-2/m)¹

Hence true for n =1

let it be true for n =k

Then E(xk-m/2/x0 =i) = (i-m/2) (1-2/m)^k

Consider n = k+1

E(xk+1-m/2/x0 =i) = (i-m/2) (1-2/m)^k(1-2/m) by recurring relation

= (i-m/2) (1-2/m)^k+1

Thus true for n =k+1

Hence proved by induction