Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-05T10:53:31.721Z 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: Topological dynamics Stochastic processes Special processes Markov 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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