Search code examples
transitionmarkov-chainsmarkovmarkov-models

Transition matrix of absorbing higher order markov chain

I have a absorbing Markov chain, let say I have the states
s={START, S1, S2, END1, END2}
The state Start will always be the starting point of the chain, however it will not be possible to return to this states once you leave it.
I am curious of how the transition matrix will look like for a absorbing higher order markov chain.

Now imagine I set up the second order Markov chain transition matrix as follwing:

__________C1 C2 C3 START END1 END2
C1,C1
C1,C2
C1,START
C1, END1
C1, END2
.
.
.

How will it look like for instance on C1, START? This will be zero for all columns, but isnt the row required to sum to 1? Do I simply remove this from the matrix?
And also how will it be for C1, END1, this row will also have zero all across? The state END1 and END2 on the other side will be impossible to leave once you are in it i.e. they are absorbing.

I wonder how the transistion matrix will look like for a second or kth order Markov chain. I cannot find any good litterature on this problem, please contribute with som good litterature.

Solution

  • The (C1, START) row should be removed from the matrix. This is because the state (C1, START) doesn't exist in the graph describing the chain. The reason it doesn't exist is simply that the state isn't reachable and hence shouldn't be considered a valid state.

    In general, the transition matrix representing the kth order Markov chain should not contain the rows of invalid k-tuples (tuples representing a sequence of states corresponding to an impossible path).

    As for the (C1, END1) row, it's not an all zero row because when you're at END1 your next state is END1 with a probability of 1. Hence, from (C1, END1) you have a non-zero probability to step into (END1, END1).