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 → ∞.
In this paper, a characterization of the aperiodicity in existential terms of some state
is given. At the same time, a P system 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 formal verification of this solution is presented and a comparative analysis with respect
to another known solution is described.