An absorbing Markov Chain has 5 states where states #1 and #2 are absorbing stat

Question

An absorbing Markov Chain has 5 states where states #1 and #2 are absorbing states and the following transition probabilities are known P3,2-0.1, P3, 3-0.4, P3,5-0.5 p4, 1-0.1, p4,3#0.5, p44#0.4 P5,1-0.3,Ps,2 0.2, P5,4-0.3, P5,s-0.2 (a) Let T denote the transition matrix. Compute T. Find the probability that if you start in state #3 you will be in state #5 after 3 steps. (b) Compute the matrix N = (1-Q)-1 Find the expected value for the number of steps prior to hitting an absorbing state if you start in state #3. (Hint: This will be the sum of one of the rows of N.) steps (c) Compute the matrix B-NR. Determine the probability that you eventually wind up in state #1 if you start in state #4.

Explanation / Answer

Create a 5-by-5 transition matrix, where the columns correspond to the respective states {#1, #2, #3, #4, #5} that can be reached next period, and the rows correspond to the respective current states in the same order as the columns. Call this matrix T. The elements of T give the conditional probabilities that being in a state of a given row, the next step will transition to the states given in columns intersecting the same row.

T =
[1.0, 0.0, 0.0, 0.0, 0.0]
[0.0, 1.0, 0.0, 0.0, 0.0]
[0.0, 0.1, 0.4, 0.0, 0.5]
[0.1, 0.0, 0.5, 0.4, 0.0]
[0.3, 0.2, 0.0, 0.3, 0.2].

Now define Tn = T^n as the then-step transition matrix. Clearly, T1 = T^1 is identical to T. In the context of this problem, n is the number of periods, or steps, for which transitions are made.

Since there are three steps involved, compute T3 = T^3.
T3 =
[1.000, 0.000, 0.000, 0.000, 0.000]
[0.000, 1.000, 0.000, 0.000, 0.000]
[0.255, 0.512, 0.083, 0.090, 0.060]
[0.447, 0.260, 0.060, 0.083, 0.150]
[0.498, 0.293, 0.090, 0.036, 0.083].

Now let s0 = [0.0, 0.0, 1.0, 0.0, 0.0] be the current, or starting state distribution (i.e., taken to be in state #3 here). Then the corresponding state distribution after three steps, s3, can be determined by
s3 = s0 T3
= [0.255, 0.512, 0.083, 0.090, 0.060].

The probability of being in state #5 after three steps are
s3(5) = 0.060.

==============

(b) You can partition T into components (sometimes requiring reordering rows and columns), so that it can be written as
T =
[ I , Z]
[R, Q],

where

Q =
[0.2, 0.0, 0.5]
[0.5, 0.2, 0.0]
[0.0, 0.3, 0.2]
gives the (single-step) transition probabilities from transient states to transient states,

R =
[0.0, 0.3]
[0.3, 0.0]
[0.3, 0.2]
gives the transition probabilities from transient states to absorbing states,

I =
[1, 0]
[0, 1]
is an identity matrix, representing that absorbing states only transition back to themselves, and

Z =
[0.0, 0.0, 0.0]
[0.0, 0.0, 0.0]
is often represented with a boldface 0, representing that absorbing states do not transition to transient states.

To see these components together within the transistion matrix T, it's often helpful to draw lines between them indicating their boundaries. Observe that the block form representation of T,

[ I , Z]
[R, Q],

becomes apparent in the original matrix T,

[1.0, 0.0, | 0.0, 0.0, 0.0]
[0.0, 1.0, | 0.0, 0.0, 0.0]
- - - - - - - | - - - - - - - - - -
[0.0, 0.1, | 0.4, 0.0, 0.5]
[0.1, 0.0, | 0.5, 0.4, 0.0]
[0.3, 0.2, | 0.0, 0.3, 0.2].

For then-step transition matrix Tn you can easily verify that in its partitioned form, the bottom part of Tn is

[(Q^0 + Q^1 + Q^2 + Q^3 + . . . + Q^(n - 1)) R, Q^n],

and the top part is still

[I, Z].

As n approaches infinity,
Q^n ? 0(Q) (where 0(Q) is a matrix of zeros of the same size as Q), and
(Q^0 + Q^1 + Q^2 + Q^3 + . . . + Q^(n - 1)) ? (I(Q) - Q)^(-1) (where I(Q) is an identity matrix of the same size as Q).

It's convenient to write N = (I(Q) - Q)^(-1), which is sometimes called the fundamental matrix for the absorbing chain. The elements of N give the expected number of steps before reaching an absorbing state, with the particular row indicating where the chain began, and the particular column corresponding to a possible transient state.

Computing N and then summing its first row gives the expected number of steps prior to hitting an absorbing state if you start in state #3. (The reason for using the first row of N is that it corresponds to state #3, since the first two rows of T are used for the absorbing states which are not part of N. Be careful not to identify state #3 with the third row of N unless you also partition the transient states first instead of absorbing states.)
I(Q) - Q =
[1 - 0.2, 0 - 0.0, 0 - 0.5]
[0 - 0.5, 1 - 0.2, 0 - 0.0]
[0 - 0.0, 0 - 0.3, 1 - 0.2] =

[ 0.8, 0.0,-0.5]
[-0.5, 0.8, 0.0]
[ 0.0,-0.3, 0.8],

so N = (I(Q) - Q)^(-1) =
[1.464531, 0.343249, 0.915332]
[0.915332, 1.464531, 0.572082]
[0.343249, 0.549199, 1.464531].
=============
c)

E(number of steps before hitting an absorbing state | start in state #3)
= N(1, 1) + N(1, 2) + N(1, 3)
= 1.464531 + 0.343249 + 0.915332
= 2.72

[0.377574, 0.622426]
[0.610984, 0.389016]
[0.604119, 0.395881].

Prob(wind up in state #1 | start in state #4)
= B(2, 1)
= 0.61

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.