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?


1 Answer 1


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$
    – gravitas
    Jun 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

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.