0
$\begingroup$

I'm very far removed from Linear Algebra or statistics that I honestly do not remember Markov Chains.

I'm trying to figure out this problem. Hopefully someone can tell me how to complete this. Excuse my lack to proper formatting with this question.

How is s3 even solved? I thought a Markov Chain rows has to be equal to 1. Is this even a Markov Chain Question?

Write a function answer(m) that takes an array of array of nonnegative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly.

For example, consider the matrix m:

 [
[0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal probability
[4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
[0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
[0,0,0,0,0,0],  # s3 is terminal
[0,0,0,0,0,0],  # s4 is terminal
[0,0,0,0,0,0],  # 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

$\endgroup$
  • $\begingroup$ You need to make the ij entry the probability of going from state j to state i. Then the columns will indeed add up to 1. $\endgroup$ – Ted Shifrin Sep 25 '16 at 20:38
  • $\begingroup$ Very ungoogley of you to post this ;) $\endgroup$ – David Ferris May 8 '17 at 17:48
  • $\begingroup$ Who said anything about google. i found the question in a book. ;-) $\endgroup$ – gmalenko May 17 '17 at 0:37
2
$\begingroup$

As your question is a two-part one (one regarding the matrix being a Markov one, and another about calculating S3) I'll try to answer both separately:

Being an Absorbing Markov matrix:

The matrix is actually missing a bit in order to be a classic Markov one. It should've been: (following the same format)

[0,1,0,0,0,1] - S0
[4,0,0,3,2,0] - S1
[0,0,1,0,0,0] - S2
[0,0,0,1,0,0] - S3
[0,0,0,0,1,0] - S4
[0,0,0,0,0,1] - S5

or to display it nice and pretty along with the transient and absorbing states and split into Q, R and I matrices :

$$ \left[ \begin{array}{cc|cccc} 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ \frac{4}{9} & 0 & 0 & \frac{3}{9} & \frac{2}{9} & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right] $$

Hopefully this answered the Markov Chain part of the question.

Solving S3

This particular one can easily be solved in another way too - here is another simplified way to solve S3:

The trouble with this table is that there is a loop between S1 and S0 - there is a 1/2 * 4/9 = 2/9 chance of looping again.

To eliminate the loop reduce the probability of s0->s1 by 2/9 and redistribute (increase) the chance to even out the possible transitions from this state.

calculating the new s0->s1 : $$ s01 = \frac{\frac{1}{2} - \frac{2}{9}}{1 - \frac{2}{9}} = \frac{\frac{5}{18}}{\frac{7}{9}} = \frac{5}{18}*\frac{9}{7} = 5/14 $$

After which you end up with:

[0,5,0,0,0,9] - S0
[0,0,0,3,2,0] - S1
[0,0,1,0,0,0] - S2
[0,0,0,1,0,0] - S3
[0,0,0,0,1,0] - S4
[0,0,0,0,0,1] - S5

or as a Markov matrix:

$$ \left[ \begin{array}{cc|cccc} 0 & \frac{5}{14} & 0 & 0 & 0 & \frac{9}{14} \\ 0 & 0 & 0 & \frac{3}{5} & \frac{2}{5} & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right] $$

and to answer how is s3 calculated:

s3 = 1 * probability_of_0_to_1 * probability_of_1_to_3 , or

$$ s3 = \frac{5}{14} * \frac{3}{5} = \frac{3}{14}$$

$\endgroup$
  • $\begingroup$ I also had to self teach this similar issue. This example was very helpful in figuring out the "how" behind the mathematics. I was able to extrapolate this to other problems, but ran into an issue on another scenario. In this example, if you have mulitiple ways to get to s3, from other steps reachable from s1, how would this translate to the last equation, do you simply multiply in say, s2_to_s3 probability assuming the s2 math is repeatable from the s1 math in he previous step? $\endgroup$ – Clint L Feb 21 '17 at 15:11
  • $\begingroup$ When you calculate the new s0->s1 where does the denominator of 1 - 2/9 come from? I understand how you get the 2/9 and why you subtract it from 1/2 but why are we subtracting it from 1 in the denominator? $\endgroup$ – landocalrissian Nov 7 '18 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.