Published April 27, 2021
| Version v1
Publication
P Systems Computing the Period of Irreducible Markov Chains
Description
It is well known that any irreducible and aperiodic Markov chain has
exactly one stationary distribution, and for any arbitrary initial distribution, the se-
quence 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 irre-
ducible 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 in-
put. A comparative analysis with respect to another known solution is described.
Abstract
Ministerio de Educación y Ciencia TIN2006–13425Abstract
Junta de Andalucía P08-TIC-04200Additional details
Identifiers
- URL
- https://idus.us.es/handle//11441/107878
- URN
- urn:oai:idus.us.es:11441/107878