Is it possible to reverse probabilistic automaton?

Question

Is it possible to reverse probabilistic automaton (PA), i.e. calculate the probability of previous state given current state? Will reversed automaton be a PA (Markov?), i.e. will next probability depend on current state only? If not, then what it will be?

Answer 1

Reversibility of a Markov Chain is not always possible. There is a characterization though, if the chain is irreducible (i.e. every state can be reached from any other state) with the stochastic matrix $P$ and the initial probability $\lambda$ vector satisfying the "detailed balance equations": $$ \lambda_i p_{ij} = \lambda_j p_{ji}$$ the chain is reversible. In particular this implies that $\lambda$ is a invariant probability measure, so reversibility can't always happen.