Consider a Markov chain with states 0, 1, n and with transition probabilities P -{156 = ifj-i-1 if j = i + k(i), = (i=1,.,n 1; Poo P1),

where k(i) 0. Let

f, denote the probability that this Markov chain ever enters state 0 given that it starts in state i Show that

f, is an increasing function of (c), .., C-1). (Hint Consider two such chains, one having (C, ., C-1) and the other (C,. ., C-1), where

c, c, Sup- pose both start in state i Couple the processes so that the next state of the first is no less than that of the second. Then let the first chain run (keeping the second one fixed) until it is either in the same state as the second one or in state n. If it is in the same state, start the procedure over.)