P Systems Computing the Period of Irreducible Markov Chains
Keywords:
Markov chain, P Sytems, Membrane ComputingAbstract
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
P. Brémaud: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York, 1998.
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
O. Häggstöm: Finite Markov Chains and Algorithmic Applications. London Mathematical Society, Cambridge University Press, Cambridge, 2003.
R. Nelson: Probability, Stochastic Processes, and Queing Theory. Springer, New York, 1995. http://dx.doi.org/10.1007/978-1-4757-2426-4
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
