3
$\begingroup$

I need help identifying what algorithm I need to solve a problem. I'm not asking for programming help here, just identifying the algorithm.

Each row of a matrix represents a state. Each element corresponds to the count of how often the current state transitions to another state. Some states are final states and do not transition at all. Some states are not reachable. There is always at least one path to one of the final states.

I need to calculate the probability of reaching all of the reachable final states and the probability for each final state.

To make this explicit here is an example of what I'm trying to accomplish.

State matrix: $$ \begin{bmatrix} 0& 1& 0& 0& 0& 1 \\ 4& 0& 3& 2& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \end{bmatrix} $$

  • First state is always 0.
  • State 1 is non-terminal.
  • State 2 has probability of 0.
  • State 3 has probability of 3/14.
  • State 4 has probability of 2/14 or 1/7.
  • State 5 has probability of 9/14.

If this is a stationary distribution, then that's what I need to code to solve the problem. If not is it something else.

Improve this question
$\endgroup$
7
  • $\begingroup$ Maybe you're looking for something like this?. $\endgroup$
    – Aristu
    Dec 16, 2016 at 3:14
  • $\begingroup$ Not sure if that's right. The data isn't in markov chain form (though i guess i could convert?) and we know it has to terminate and not be a full chain. I guess that's why i'm asking, i don't know if that's the right algorithm or not. $\endgroup$
    – cryptoref
    Dec 16, 2016 at 4:11
  • $\begingroup$ So you want the stationary distribution of a Markoiv chain? If not, please clarify what the difference is. $\endgroup$
    – Raphael ♦
    Dec 16, 2016 at 6:09
  • $\begingroup$ I'm learning here so i'm going to study up on stationary distribution of the Markov chain. Hopefully that will send me in the right direction. $\endgroup$
    – cryptoref
    Dec 16, 2016 at 8:05
  • 2
    $\begingroup$ Your example makes no sense. The zero probability state you should be state 4. $\endgroup$
    – Yuval Filmus
    Dec 16, 2016 at 9:48

1 Answer 1

Reset to default
4
$\begingroup$

Take your matrix, and normalize the rows to sum to 1. Denote the result by $A$; in your example, $$ A = \begin{bmatrix} 0& 1/2& 0& 0& 0& 1/2 \\ 4/9& 0& 1/3& 2/9& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \end{bmatrix} $$ Let $v$ be a row vector with $v_0 = 1$ and $v_i = 0$ otherwise. In your example, $$ v = \begin{bmatrix} 1&0&0&0&0&0 \end{bmatrix} $$ Then $vA^t$ gives the probabilities of being in each state after $t$ steps, and so $w := v \sum_{t=0}^\infty A^t$ gives the expected number of times in each state. Since a final state terminates the process, for each final state $i$, $w_i$ is in fact the probability of the process ending at $i$. The vector $w$ can be calculated using the formula $$ w = v (I-A)^{-1}. $$ In your case, we get $$ w = \begin{bmatrix} 9/7 & 9/14 & 3/14 & 1/7 & 0 & 9/14 \end{bmatrix} $$ In particular, the probabilities of terminating at the final states $2,3,4,5$ are (respectively) $3/14,1/7,0,9/14$.

Regarding algorithms, we can rephrase the problem as follows: given $v,A$, find the vector $w$ such that $$ w(I-A) = v. $$ This requires solving a system of linear equations, for which there are many algorithms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you so much. As i said i'm learning here so a couple of ideas just caught on, but i have a few more questions. The big point was that the terminal state wi is the probability. Thanks. I'm unfamiliar with the math so i'm assuming that I and A are "standard" terms. Where should i look to be able to find how to calculate them? $\endgroup$
    – cryptoref
    Dec 16, 2016 at 19:02
  • $\begingroup$ $A$ is the input matrix with non-zero rows normalized so that they sum to 1 (as in the example) and $I$ is the identity matrix. I suggest reviewing linear algebra. $\endgroup$
    – Yuval Filmus
    Dec 16, 2016 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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