Suppose A and B are each ergodic Markov chains with transition prob- abilities {PAi,Aj } and {PBi,Bj } respectively. Denote the steady-state probabilities of A and B by {πAi } and {πBi } respectively. The chains are now connected and modified as shown below. In particular, states A1 and B1 are connected and the new transition probabilities P∗ for the combined chain are given by
A1,B1 = ε, PA1,Aj = (1 - ε)PA1,Aj for all Aj;
P∗ ∗
B1,A1 = δ, PB1,Bj = (1 - δ)PB1,Bj for all Bj.
P∗ ∗
All other transition probabilities remain the same. Think intuitively of ε and δ as being small, but do not make any approximations in what follows. Give your answers to the following questions as functions of ε, δ, {πAi } and {πBi }.
Chain A Chain B
(a) Assume that E > 0, δ = 0 (i.e., that A is a set of transient states in the combined chain). Starting in state A1, find the conditional expected time to return to A1 given that the first transition is to some state in chain A.
(b) Assume that E > 0, δ = 0. Find TA,B, the expected time to first reach state B1 starting from state A1. Your answer should be a function of E and the original steady-state probabilities {πAi } in chain A.
(c) Assume ε > 0, δ > 0. Find TB,A, the expected time to first reach state A1, starting in state B1. Your answer should depend only on δ and {πBi }.
(d) Assume ε > 0 and δ > 0. Find P∗(A), the steady-state probability that the combined chain is in one of the states {Aj} of the original chain A.
(e) Assume ε > 0, δ = 0. For each state Aj /= A1 in A, find vAj , the expected number of visits to state Aj, starting in state A1, before reaching state B1. Your answer should depend only on ε and {πAi }.
(f) Assume ε > 0, δ > 0. For each state Aj in A, find π ∗ , the steady-state probability of being in state Aj in the combined chain. Hint: Be careful in your treatment of state A1.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.