I am participating in a python coding challenge. It was going well but this question stumped me.
Consider the matrix m: [0,1,0,0,0,1], [4,0,0,3,2,0], [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0]
s0, the initial state, goes to s1 and s5 with equal probability s1 can become s0, s3, or s4, but with different probabilities s2 is terminal, and unreachable (never observed in practice) s3 is terminal s4 is terminal s5 is terminal So, we can consider different paths to terminal states, such as:
- s0 -> s1 -> s3
- s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
- s0 -> s1 -> s0 -> s5
Tracing the probabilities of each, we find that
- s2 has probability 0
- s3 has probability 3/14
- s4 has probability 1/7
- s5 has probability 9/14
How were these probabilities found?
Simply put, it's an absorbing markov chain. So far so good.
The first tricky thing is that the matrix does not have the probability of the next state, but rather the number of observations. It's simple enough to get the probability from that by dividing by the sum, however, the answer needs to be in FRACTION format.
The second thing that got me was that I am getting the wrong probabilities for the terminal states.
So my question is: Given the above matrix, how do I calculate the probability of the terminal states and how do I keep it in fraction form?