1
$\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.

$\endgroup$
  • $\begingroup$ Maybe you're looking for something like this?. $\endgroup$ – Aristu Dec 16 '16 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 '16 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 '16 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 '16 at 8:05
  • 1
    $\begingroup$ Your example makes no sense. The zero probability state you should be state 4. $\endgroup$ – Yuval Filmus Dec 16 '16 at 9:48
1
$\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.

$\endgroup$
  • $\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 '16 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 '16 at 20:03

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.