patternMinor
What algorithm to find end state probabilities
Viewed 0 times
findwhatalgorithmprobabilitiesstateend
Problem
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}
$$
If this is a stationary distribution, then that's what I need to code to solve the problem. If not is it something else.
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.
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#67487, answer score: 4
Revisions (0)
No revisions yet.