Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T13:09:23.354Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic cellular automata with general alphabets possessing a Markov chain as an invariant distribution

Part of: Markov processes Special processes Topological dynamics Stochastic processes

Published online by Cambridge University Press:  10 June 2016

Jérôme Casse
Jérôme Casse*
Affiliation:
Université de Bordeaux
*
* Postal address: LaBRI, Université de Bordeaux, 351 cours de Libération, 33405 Talence cedex, France. Email address: jerome.casse@univ-lorraine.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper is devoted to probabilistic cellular automata (PCAs) on N,Z or Z / nZ, depending on two neighbors with a general alphabet E (finite or infinite, discrete or not). We study the following question: under which conditions does a PCA possess a Markov chain as an invariant distribution? Previous results in the literature give some conditions on the transition matrix (for positive rate PCAs) when the alphabet E is finite. Here we obtain conditions on the transition kernel of a PCA with a general alphabet E. In particular, we show that the existence of an invariant Markov chain is equivalent to the existence of a solution to a cubic integral equation. One of the difficulties in passing from a finite alphabet to a general alphabet comes from the problem of measurability, and a large part of this work is devoted to clarifying these issues.

Keywords

Probabilistic cellular automatainvariant measureMarkov chain

MSC classification

Primary: 37B15: Cellular automata 60G10: Stationary processes 60J05: Discrete-time Markov processes on general state spaces
Secondary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 2 , June 2016 , pp. 369 - 391
Copyright
Copyright © Applied Probability Trust 2016 

References

[1]Albenque, M. (2009).A note on the enumeration of directed animals via gas considerations.Ann. Appl. Prob. 19,1860–1879.Google Scholar
[2]Belyaev, Y. K.,Gromak, Y. I. and Malyshev, V. A. (1969).Invariant random Boolean fields.Math. Notes Acad. Sci. USSR 6,792–799.Google Scholar
[3]Blank, M. (2012).Stochastic stability of traffic maps.Nonlinearity 25,3389–3408.Google Scholar
[4]Bousquet-Mélou, M. (1998).New enumerative results on two-dimensional directed animals.Discrete Mathematics 180,73–106.Google Scholar
[5]Briceño, R.,Moisset de Espanés, P.,Osses, A. and Rapaport, I. (2013).Solving the density classification problem with a large diffusion and small amplification cellular automaton.Physica D 261,70–80.CrossRefGoogle Scholar
[6]Casse, J. and Marckert, J.-F. (2015).Markovianity of the invariant distribution of probabilistic cellular auomata on the line.Stoch. Process. Appl. 125,3458–3483.Google Scholar
[7]Ceccherini-Silberstein, T. and Coornaert, M. (2013).Surjunctivity and reversibility of cellular automata over concrete categories. In Trends in Harmonic Analysis,Springer,Milan, pp.91–133.Google Scholar
[8]Derrida, B.,Domany, E. and Mukamel, D. (1992).An exact solution of a one-dimensional asymmetric exclusion model with open boundaries.J. Statist. Phys. 69,667–687.CrossRefGoogle Scholar
[9]Durrett, R. (2010).Probability: Theory and Examples,4th edn.Cambridge University Press.CrossRefGoogle Scholar
[10]Flajolet, P. and Sedgewick, R. (2009).Analytic Combinatorics.Cambridge University Press.Google Scholar
[11]Hedlund, G. A. (1969).Endomorphisms and automorphisms of the shift dynamical system.Math. Systems Theory 3,320–375.CrossRefGoogle Scholar
[12]Kesten, H. (1987).Percolation theory and first-passage percolation.Ann. Prob. 15,1231–1271.Google Scholar
[13]Kozlov, and Vasilyev, (1980).Reversible Markov chains with local interaction. In Multicomponent Random Systems (Adv. Prob. Relat. Topics 6),Dekker,New York, pp.451–469.Google Scholar
[14]Mairesse, J. and Marcovici, I. (2014).Around probabilistic cellular automata.Theoret. Comput. Sci. 559,42–72.Google Scholar
[15]Mairesse, J. and Marcovici, I. (2014).Probabilistic cellular automata and random fields with i.i.d. directions.Ann. Inst. H. Poincaré Prob. Statist. 50,455–475.CrossRefGoogle Scholar
[16]Meyn, S. and Tweedie, R. L. (2009).Markov Chains and Stochastic Stability,2nd edn.Cambridge University Press.Google Scholar
[17]Pra, P. D.,Louis, P.-Y. and Roelly, S. (2002).Stationary measures and phase transition for a class of probabilistic cellular automata.ESAIM Prob. Statist. 6,89–104.CrossRefGoogle Scholar
[18]Schiff, J. L. (2008).Cellular Automata: A Discrete View of the World.John Wiley,Hoboken, NJ.Google Scholar
[19]Toom, A. L.et al. (1990).Part I: Discrete local Markov systems. In Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis, eds R. L. Dobrushin et al.,Manchester University Press, pp.1–182.Google Scholar
[20]Vancheri, A.,Giordano, P.,Andrey, D. and Albeverio, S. (2005).Continuous valued cellular automata and decision process of agents for urban dynamics. In Computers in Urban Planning and Urban Management (CUPUM 2005), Paper 293.Google Scholar
[21]Vasilyev, N. B. (1978).Bernoulli and Markov stationary measures in discrete local interactions. In Development in Statistics, Vol. 1,Academic Press,New York, pp.99–112.Google Scholar
[22]West, M. and Harrison, J. (1997).Bayesian Forecasting and Dynamic Models,2nd edn.Springer,New York.Google Scholar