<p>Suppose we have $N$ states</p>

<p>$q_i$, $0\leq i&lt;N$</p>

<p>Suppose we have $N\times N$ probability matrix</p>

<p>$p_{ij}$, $0\leq i&lt;N$, $0\leq j&lt;N$, </p>

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

<p>Question #1: is this what is called "probabilistic automaton"?</p>

<p>Next.</p>

<p>We can introduce another interpretation: represent each state of a machine as a column of values</p>

<p>$w_i$, $0\leq i&lt;N$</p>

<p>each representing a "weight" of previously defined state $q_i$.</p>

<p>If machine is completely in state $q_0$ then we have</p>

<p>$w_i=1, i=0$</p>

<p>$w_i=0, i\neq0$</p>

<p>and so on.</p>

<p>In this interpretation each state change is just changing of the weights of a state column</p>

<p>$w_i \rightarrow p_{ij} w_i$</p>

<p>assumming summation by.</p>

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

CC BY-SA 3.0
2013-07-05T11:04:52.937Z
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.
Klaus Draeger
CC BY-SA 3.0
2013-07-05T11:32:10.223Z
Are these matrices chosen by input symbols? Or by previous states history? Or randomly?
Suzan Cioc
CC BY-SA 3.0
2013-07-05T11:42:10.423Z
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.
Klaus Draeger
CC BY-SA 3.0
2013-07-05T14:37:08.950Z
@KlausDraeger: with the latter comment you mean that there may be an internal non-determinism as well?
SBF
<automata-theory><probabilistic-automata>
Vector representation of probabilistic automaton
Suzan Cioc
# Vector representation of probabilistic automaton

(Asked by: username_0 on 2013-07-05)

Suppose we have $N$ states

$q\_i$, $0\leq i

Suppose we have $N\times N$ probability matrix

$p\_{ij}$, $0\leq i

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"?

Next.

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

$w\_i$, $0\leq i

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?

**Tags:** automata-theory, probabilistic-automata
> **Comments:**
> **username_1**: 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.  
> **username_0**: Are these matrices chosen by input symbols? Or by previous states history? Or randomly?  
> **username_1**: 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.  
> **username_2**: @KlausDraeger: with the latter comment you mean that there may be an internal non-determinism as well?  

---

## 0 answers

