P Systems Computing the Period of Irreducible Markov Chains

  • Mónica Cardona-Roca Dpt. of Mathematics, University of Lleida Av. Alcalde Rovira Roure, 191. 25198 Lleida, Spain
  • M. Ángels Colomer-Cugat Dpt. of Mathematics, University of Lleida Av. Alcalde Rovira Roure, 191. 25198 Lleida, Spain
  • Agustín Riscos-Núñez Research Group on Natural Computing Dpt. of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
  • Miquel Rius-Font Department of Applied Mathematics IV Universitat Politécnica de Catalunya Edifici C3, Despatx 016, Av. del Canal Olímpic, s/n, 08860 Castelldefels, Spain

Abstract

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.

References

[1] P. Brémaud: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York, 1998.

[2] M. Cardona, M.A. Colomer, M.J. Pérez–Jiménez, A. Zaragoza: Classifying states of a finite Markov chains with membrane computing. Lecture Notes in Computer Science. Springer,Vol 4361, pp. 266- 278, 2006.
http://dx.doi.org/10.1007/11963516_17

[3] O. Häggstöm: Finite Markov Chains and Algorithmic Applications. London Mathematical Society, Cambridge University Press, Cambridge, 2003.

[4] R. Nelson: Probability, Stochastic Processes, and Queing Theory. Springer, New York, 1995.
http://dx.doi.org/10.1007/978-1-4757-2426-4
Published
2009-09-01
How to Cite
CARDONA-ROCA, Mónica et al. P Systems Computing the Period of Irreducible Markov Chains. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 4, n. 3, p. 291-300, sep. 2009. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2437>. Date accessed: 23 nov. 2020. doi: https://doi.org/10.15837/ijccc.2009.3.2437.

Keywords

Markov chain, P Sytems, Membrane Computing