Suppose we have $N$ states

$q_i$, $0\leq i<N$

Suppose we have $N\times N$ probability matrix

$p_{ij}$, $0\leq i<N$, $0\leq j<N$,

And suppose a machine, which is being in state $q_i$ then goes to state $q_j$ with probability $p_{ij}$.

Question #1: is this what is called "probabilistic automaton"?


We can introduce another interpretation: represent each state of a machine as a column of values

$w_i$, $0\leq i<N$

each representing a "weight" of previously defined state $q_i$.

If machine is completely in state $q_0$ then we have

$w_i=1, i=0$

$w_i=0, i\neq0$

and so on.

In this interpretation each state change is just changing of the weights of a state column

$w_i \rightarrow p_{ij} w_i$

assumming summation by.

Question #2: it this a precise interpretation of previous PA? If each first interpretation corresponds with second and vice versa?

  • 1
    $\begingroup$ Regarding #1: What you are describing is a (discrete time) Markov chain. In a nutshell, the difference to PA is that the latter also feature nondeterminism, i.e. you actually have several probability matrices (usually labelled by some actions) between which you can choose in each step. $\endgroup$ – Klaus Draeger Jul 5 '13 at 11:04
  • $\begingroup$ Are these matrices chosen by input symbols? Or by previous states history? Or randomly? $\endgroup$ – Suzan Cioc Jul 5 '13 at 11:32
  • 1
    $\begingroup$ It depends on what you want to model - often, the question is about the minimum/maximum probability of some class of behaviors (like those reaching a given set of goal states). Then the choice is assumed to be made by a minimizing/maximizing strategy (and the question boils down to finding this strategy). This strategy can take the history into account (though this is not necessary for mere reachability). The symbols in general don't uniquely determine a successor distribution; there is a related model (Markov decision processes), where they do. $\endgroup$ – Klaus Draeger Jul 5 '13 at 11:42
  • $\begingroup$ @KlausDraeger: with the latter comment you mean that there may be an internal non-determinism as well? $\endgroup$ – Ilya Jul 5 '13 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.