Suppose I have a Finite State Automata with various states and probabilities of state transitions. Does mathematics exist to determine the probability of NOT reaching a state in the FSA given some n number of state changes?
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Nothing new is needed.
First note that the chance of not being in the state exactly at transition $n$ is the complement of the chance of being in the state at transition $n$.
The chance of never encountering the state at some point during the first $n$ transitions is almost as simple to find. Modify the FSA by redirecting all outgoing transitions from that state back to itself so it becomes a terminal (absorbing) state. The chance of being in that state at transition $n$ in the modified FSA is the chance of encountering that state at some point during the first $n$ transitions in the original FSA. The complement of this chance is the desired probability.
-
$\begingroup$ Right, that makes sense. I am new to this however, and I am not sure how to determine the desired probability of ending up in the state in this modified FSA after n iterations. Can you provide some methods or insight? $\endgroup$– gravitasJun 26, 2014 at 3:39
-
1$\begingroup$ You compute the $n^\text{th}$ power of the transition matrix and inspect the relevant entry. For small $n$ this is elementary, as illustrated at stats.stackexchange.com/questions/45920. A standard, more sophisticated method diagonalizes the transition matrix: see stats.stackexchange.com/questions/87385. $\endgroup$– whuber ♦Jun 26, 2014 at 3:43