Assume a friend has developed an excellent program for finding the steady-state probabilities for finite-state Markov chains. More precisely, given the transition matrix [P], the program returns limn Pn for each i. Assume all chains are aperiodic.

(a) You want to find the expected time to first reach a given state k starting from a different state m for a Markov chain with transition matrix [P]. You modify the matrix to [P∗] where P∗ = 1, P∗ = 0 for j /= m, and P∗ = Pij  otherwise. How do you find the desired first-passage time from the program output given [P∗] as an input? Hint: The times at which a Markov chain enters any given state can be considered as renewals in a (perhaps delayed) renewal process.

(b) Using the same [P∗] as the program input, how can you find the expected number of returns to state m before the first passage to state k?

(c) Suppose, for the same Markov chain [P] and the same starting state m, you want to find the probability of reaching some given state n before the first passage to k. Modify [P] to some [P∗∗] so that the above program withP∗∗ as an input allows you to easily find the desired probability.

(d) Let Pr{X(0) = i} = Qi, 1  ≤ i  ≤ M be an arbitrary set of initial probabilities for the same Markov chain [P] as above. Show how to modify [P] to some [P∗∗∗] for which the steady-state probabilities allow you to easily find the expected time of the first passage to state k.

Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.