I am looking for a stochastic automaton, which induces the same probability $c \in [0,1]$ for all words in $\Sigma^*$, where $\Sigma$ is some finite alphabet.
A stochastic automaton over an alphabet $\Sigma$ is a tuple $\mathcal A$= { $\mathcal Q$, $\Sigma$, $\pi$, $(P_a)_{a\in \Sigma}$, $\mathcal f$} where
- $\mathcal Q = \{1,2,...,n\}$ is a finite set of states
- $\pi \in [0,1]$ with $\sum_{i=1}^n \pi_i = 1 $ (inital probability distribution)
- for each $a \in \Sigma$, $P_a$ is a $n \times n$ transition matrix taking values in $[0,1]$ such that for all row $i = 1,...,n$ we have $\sum_{i=1}^n (P_a)_{ij} = 1 $
- $f \in [0,1]^{n \times 1}$ is the final state vector such that $f(i) = 1$ iff state $i$ is final.
If $\pi = (p_1,..., p_n)$ is the initital distribution, the probability to reach state $j$ by reading a word $w = a_1 ... a_n $ $\in \Sigma$ is given by $(\pi \cdot P_w )_j = \sum_{i=1}^n \pi_i \cdot (P_w)_{ij}$
If the automaton $\mathcal A$ has $f = (f_1,..., f_n) $ as a final vector, it is then in a final state with the probability $\sum_{i=1}^n (\pi_i \cdot P_w)_{j} \cdot f_i = \pi \cdot P_w \cdot f$.
Example: $w = aab$ $\Rightarrow $ $\pi \cdot P_w \cdot f = \pi \cdot P_a² \cdot P_b \cdot f$
I constructed the following automaton so that every word has the same probability.
$\mathcal Q = \{1\}$, $\pi = \left( \begin{array}{cc} 1\\ \end{array} \right) $ , $f = \left( \begin{array}{cc} 1\\ \end{array} \right) $, $P_\epsilon = \left( \begin{array}{cc} 1 \\ \end{array} \right) $and $P_\Sigma = \left( \begin{array}{cc} 1\\ \end{array} \right) $.
Then $\pi \cdot P_{\Sigma^*}^n \cdot f = 1 = c $ But in this case $c = 1$ and not arbitrary.
My observations:
- $2$ states are necessary since
- the probability c has to be split in $1-c$ and c for $a \in \Sigma$ transitions
- there are different options to involve c: In $\pi$, $P_\Sigma*$ and/or in $f$
Can anybody give me a hint?
Let $P$ be the $2\times 2$ identity, $\pi=(c,1-c)$, $f=(1,0)$. Then all words have the same probability $c$ of being accepted.