2

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?

gravitas
  • 121
  • 2

1 Answers1

5

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.

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • 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? – gravitas Jun 26 '14 at 03:39
  • 1
    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 http://stats.stackexchange.com/questions/45920. A standard, more sophisticated method diagonalizes the transition matrix: see http://stats.stackexchange.com/questions/87385. – whuber Jun 26 '14 at 03:43