Assume a friend has developed an excellent program for finding the steady-state probabilities for finite-state Markov chains. More precisely, given the tran- sition matrix [P], the program returns limn P
n
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∗
=
P
ij
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 with
P∗∗ as an input allows you to easily find the desired probability.
(d)
Let Pr{X(0) =
i} =
Q
i, 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.