Research Group on Natural Computing

It is well known that any irreducible and aperiodic Markov chain has exactly one stationary distribution, and for any arbitrary initial distribution, the sequence of distributions at time n converges to the stationary distribution, that is, the
Markov chain is approaching equilibrium as n tends to infinity.
In this paper, a characterization of the aperiodicity in existential terms of some state is
given. At the same time, a Psystem with external output is associated with any irreducible Markov chain. The designed system provides the aperiodicity of that Markov chain and spends a polynomial amount of resources with respect to the size of the input. A comparative analysis with respect to another known solution is described.