Random \mathbb{Z}^d-shifts of finite type

Previous Article
An Urysohn-type theorem under a dynamical constraint
JMD Home
This Volume
Next Article
The entropy of Lyapunov-optimizing measures of some matrix cocycles

2016, 10: 287-330. doi: 10.3934/jmd.2016.10.287

Random $\mathbb{Z}^d$-shifts of finite type

Kevin McGoff ^1, and Ronnie Pavlov ^2,

1.	Department of Mathematics and Statistics, The University of North Carolina at Charlotte, 9201 University City Blvd., Charlotte, NC 28223, United States
2.	Department of Mathematics, University of Denver, 2280 S. Vine St., Denver, CO 80208, United States

Received August 2014 Revised January 2016 Published July 2016

Abstract
Related Papers

In this work we consider an ensemble of random $\mathbb{Z}^d$-shifts of finite type ($\mathbb{Z}^d$-SFTs) and prove several results concerning the behavior of typical systems with respect to emptiness, entropy, and periodic points. These results generalize statements made in [26] regarding the case $d=1$.
Let $\mathcal{A}$ be a finite set, and let $d \geq 1$. For $n$ in $\mathbb{N}$ and $\alpha$ in $[0,1]$, define a random subset $\omega$ of $\mathcal{A}^{[1,n]^d}$ by independently including each pattern in $\mathcal{A}^{[1,n]^d}$ with probability $\alpha$. Let $X_{\omega}$ be the (random) $\mathbb{Z}^d$-SFT built from the set $\omega$. For each $\alpha \in [0,1]$ and $n$ tending to infinity, we compute the limit of the probability that $X_{\omega}$ is empty, as well as the limiting distribution of entropy of $X_{\omega}$. Furthermore, we show that the probability of obtaining a nonempty system without periodic points tends to zero.
For $d>1$, the class of $\mathbb{Z}^d$-SFTs is known to contain strikingly different behavior than is possible within the class of $\mathbb{Z}$-SFTs. Nonetheless, the results of this work suggest a new heuristic: typical $\mathbb{Z}^d$-SFTs have similar properties to their $\mathbb{Z}$-SFT counterparts.

Keywords: Symbolic dynamics, subshifts of finite type, topological entropy, random dynamical systems..

Mathematics Subject Classification: Primary: 37B50; Secondary: 37B10, 37H9.

Citation: Kevin McGoff, Ronnie Pavlov. Random $\mathbb{Z}^d$-shifts of finite type. Journal of Modern Dynamics, 2016, 10: 287-330. doi: 10.3934/jmd.2016.10.287

References:

[1]	E. Abbe and A. Montanari, On the concentration of the number of solutions of random satisfiability formulas, Random Structures Algorithms, 45 (2014), 362-382. doi: 10.1002/rsa.20501.
[2]	D. Achlioptas, A. Coja-Oghlan and F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, Random Structures Algorithms, 38 (2011), 251-268. doi: 10.1002/rsa.20323.
[3]	D. Achlioptas, A. Naor and Y. Peres, Rigorous location of phase transitions in hard optimization problems, Nature, 435 (2005), 759-764. doi: 10.1038/nature03602.
[4]	D. Achlioptas and Y. Peres, The threshold for random k-SAT is $2^k\log 2-O(k)$, J. Amer. Math. Soc., 17 (2004), 947-973. doi: 10.1090/S0894-0347-04-00464-3.
[5]	R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66 (1966), 72pp.
[6]	R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, Second revised edition, With a preface by David Ruelle, Edited by Jean-René Chazottes, Lecture Notes in Mathematics, 470, Springer-Verlag, Berlin, 2008.
[7]	M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory and Dynamical Systems, 3 (1983), 541-557. doi: 10.1017/S0143385700002133.
[8]	M. Boyle, R. Pavlov and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc., 362 (2010), 4617-4653. doi: 10.1090/S0002-9947-10-05003-8.
[9]	R. Burton and J. E. Steif, Non-uniqueness of measures of maximal entropy for subshifts of finite type, Ergodic Theory Dynam. Systems, 14 (1994), 213-235. doi: 10.1017/S0143385700007859.
[10]	M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976.
[11]	N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16 (1965), 109-114. doi: 10.1090/S0002-9939-1965-0174934-9.
[12]	E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, With an appendix by Jean Bourgain, J. Amer. Math. Soc., 12 (1999), 1017-1054. doi: 10.1090/S0894-0347-99-00305-7.
[13]	G. Grimmett, Percolation, Second edition, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321, Springer-Verlag, Berlin, 1999. doi: 10.1007/978-3-662-03981-6.
[14]	M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167. doi: 10.1007/s00222-008-0161-7.
[15]	M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011-2038. doi: 10.4007/annals.2010.171.2011.
[16]	M. S. Keane, Ergodic theory and subshifts of finite type, in Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces (Trieste, 1989), Oxford Sci. Publ., Oxford Univ. Press, New York, 1991, 35-70.
[17]	B. Kitchens, Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts, Universitext, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-58822-8.
[18]	W. Krieger, On the subsystems of topological Markov chains, Ergodic Theory and Dynamical Systems, 2 (1982), 195-202. doi: 10.1017/S0143385700001516.
[19]	F. Krząkała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. USA, 104 (2007), 10318-10323. doi: 10.1073/pnas.0703685104.
[20]	S. J. Lightwood, Morphisms from non-periodic $\mathbb Z^2$-subshifts. I. Constructing embeddings from homomorphisms, Ergodic Theory Dynam. Systems, 23 (2003), 587-609. doi: 10.1017/S014338570200130X.
[21]	S. J. Lightwood, Morphisms from non-periodic $\mathbb Z^2$ subshifts. II. Constructing homomorphisms to square-filling mixing shifts of finite type, Ergodic Theory Dynam. Systems, 24 (2004), 1227-1260. doi: 10.1017/S0143385704000276.
[22]	D. Lind, A zeta function for $\mathbbZ^d$-actions, in Ergodic Theory of $\mathbbZ^d$ Actions (Warwick, 1993-1994), London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, 1996, 433-450. doi: 10.1017/CBO9780511662812.019.
[23]	D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.
[24]	D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems, 4 (1984), 283-300. doi: 10.1017/S0143385700002443.
[25]	B. Marcus, Factors and extensions of full shifts, Monatsh. Math., 88 (1979), 239-247. doi: 10.1007/BF01295238.
[26]	K. McGoff, Random subshifts of finite type, Ann. Probab., 40 (2012), 648-694. doi: 10.1214/10-AOP636.
[27]	M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math., 60 (1938), 815-866. doi: 10.2307/2371264.
[28]	W. Parry, Intrinsic Markov chains, Trans. Amer. Math. Soc., 112 (1964), 55-66. doi: 10.1090/S0002-9947-1964-0161372-1.
[29]	A. Quas and A. A. Şahin, Entropy gaps and locally maximal entropy in $\mathbb Z^d$ subshifts, Ergodic Theory Dynam. Systems, 23 (2003), 1227-1245. doi: 10.1017/S0143385702001761.
[30]	D. Ruelle, Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics, Second edition, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511617546.

show all references

References:

[1]	E. Abbe and A. Montanari, On the concentration of the number of solutions of random satisfiability formulas, Random Structures Algorithms, 45 (2014), 362-382. doi: 10.1002/rsa.20501.
[2]	D. Achlioptas, A. Coja-Oghlan and F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, Random Structures Algorithms, 38 (2011), 251-268. doi: 10.1002/rsa.20323.
[3]	D. Achlioptas, A. Naor and Y. Peres, Rigorous location of phase transitions in hard optimization problems, Nature, 435 (2005), 759-764. doi: 10.1038/nature03602.
[4]	D. Achlioptas and Y. Peres, The threshold for random k-SAT is $2^k\log 2-O(k)$, J. Amer. Math. Soc., 17 (2004), 947-973. doi: 10.1090/S0894-0347-04-00464-3.
[5]	R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66 (1966), 72pp.
[6]	R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms, Second revised edition, With a preface by David Ruelle, Edited by Jean-René Chazottes, Lecture Notes in Mathematics, 470, Springer-Verlag, Berlin, 2008.
[7]	M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory and Dynamical Systems, 3 (1983), 541-557. doi: 10.1017/S0143385700002133.
[8]	M. Boyle, R. Pavlov and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc., 362 (2010), 4617-4653. doi: 10.1090/S0002-9947-10-05003-8.
[9]	R. Burton and J. E. Steif, Non-uniqueness of measures of maximal entropy for subshifts of finite type, Ergodic Theory Dynam. Systems, 14 (1994), 213-235. doi: 10.1017/S0143385700007859.
[10]	M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976.
[11]	N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16 (1965), 109-114. doi: 10.1090/S0002-9939-1965-0174934-9.
[12]	E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, With an appendix by Jean Bourgain, J. Amer. Math. Soc., 12 (1999), 1017-1054. doi: 10.1090/S0894-0347-99-00305-7.
[13]	G. Grimmett, Percolation, Second edition, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321, Springer-Verlag, Berlin, 1999. doi: 10.1007/978-3-662-03981-6.
[14]	M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167. doi: 10.1007/s00222-008-0161-7.
[15]	M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011-2038. doi: 10.4007/annals.2010.171.2011.
[16]	M. S. Keane, Ergodic theory and subshifts of finite type, in Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces (Trieste, 1989), Oxford Sci. Publ., Oxford Univ. Press, New York, 1991, 35-70.
[17]	B. Kitchens, Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts, Universitext, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-58822-8.
[18]	W. Krieger, On the subsystems of topological Markov chains, Ergodic Theory and Dynamical Systems, 2 (1982), 195-202. doi: 10.1017/S0143385700001516.
[19]	F. Krząkała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. USA, 104 (2007), 10318-10323. doi: 10.1073/pnas.0703685104.
[20]	S. J. Lightwood, Morphisms from non-periodic $\mathbb Z^2$-subshifts. I. Constructing embeddings from homomorphisms, Ergodic Theory Dynam. Systems, 23 (2003), 587-609. doi: 10.1017/S014338570200130X.
[21]	S. J. Lightwood, Morphisms from non-periodic $\mathbb Z^2$ subshifts. II. Constructing homomorphisms to square-filling mixing shifts of finite type, Ergodic Theory Dynam. Systems, 24 (2004), 1227-1260. doi: 10.1017/S0143385704000276.
[22]	D. Lind, A zeta function for $\mathbbZ^d$-actions, in Ergodic Theory of $\mathbbZ^d$ Actions (Warwick, 1993-1994), London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, 1996, 433-450. doi: 10.1017/CBO9780511662812.019.
[23]	D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.
[24]	D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems, 4 (1984), 283-300. doi: 10.1017/S0143385700002443.
[25]	B. Marcus, Factors and extensions of full shifts, Monatsh. Math., 88 (1979), 239-247. doi: 10.1007/BF01295238.
[26]	K. McGoff, Random subshifts of finite type, Ann. Probab., 40 (2012), 648-694. doi: 10.1214/10-AOP636.
[27]	M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math., 60 (1938), 815-866. doi: 10.2307/2371264.
[28]	W. Parry, Intrinsic Markov chains, Trans. Amer. Math. Soc., 112 (1964), 55-66. doi: 10.1090/S0002-9947-1964-0161372-1.
[29]	A. Quas and A. A. Şahin, Entropy gaps and locally maximal entropy in $\mathbb Z^d$ subshifts, Ergodic Theory Dynam. Systems, 23 (2003), 1227-1245. doi: 10.1017/S0143385702001761.
[30]	D. Ruelle, Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics, Second edition, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511617546.

[1]	Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122
[2]	Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete and Continuous Dynamical Systems, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497
[3]	Silvère Gangloff. Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 931-988. doi: 10.3934/dcds.2021143
[4]	Yujun Zhu. Preimage entropy for random dynamical systems. Discrete and Continuous Dynamical Systems, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829
[5]	Xiaomin Zhou. Relative entropy dimension of topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6631-6642. doi: 10.3934/dcds.2019288
[6]	Yun Zhao, Wen-Chiao Cheng, Chih-Chang Ho. Q-entropy for general topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2059-2075. doi: 10.3934/dcds.2019086
[7]	Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete and Continuous Dynamical Systems, 2016, 36 (7) : 3705-3717. doi: 10.3934/dcds.2016.36.3705
[8]	João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465
[9]	Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487
[10]	Zhiming Li, Lin Shu. The metric entropy of random dynamical systems in a Hilbert space: Characterization of invariant measures satisfying Pesin's entropy formula. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 4123-4155. doi: 10.3934/dcds.2013.33.4123
[11]	Jakub Šotola. Relationship between Li-Yorke chaos and positive topological sequence entropy in nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5119-5128. doi: 10.3934/dcds.2018225
[12]	N. D. Cong, T. S. Doan, S. Siegmund. A Bohl-Perron type theorem for random dynamical systems. Conference Publications, 2011, 2011 (Special) : 322-331. doi: 10.3934/proc.2011.2011.322
[13]	Lianfa He, Hongwen Zheng, Yujun Zhu. Shadowing in random dynamical systems. Discrete and Continuous Dynamical Systems, 2005, 12 (2) : 355-362. doi: 10.3934/dcds.2005.12.355
[14]	Philippe Marie, Jérôme Rousseau. Recurrence for random dynamical systems. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 1-16. doi: 10.3934/dcds.2011.30.1
[15]	Xinsheng Wang, Weisheng Wu, Yujun Zhu. Local unstable entropy and local unstable pressure for random partially hyperbolic dynamical systems. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 81-105. doi: 10.3934/dcds.2020004
[16]	David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287
[17]	Alfredo Marzocchi, Sara Zandonella Necca. Attractors for dynamical systems in topological spaces. Discrete and Continuous Dynamical Systems, 2002, 8 (3) : 585-597. doi: 10.3934/dcds.2002.8.585
[18]	Philipp Gohlke, Dan Rust, Timo Spindeler. Shifts of finite type and random substitutions. Discrete and Continuous Dynamical Systems, 2019, 39 (9) : 5085-5103. doi: 10.3934/dcds.2019206
[19]	Jérôme Rousseau, Paulo Varandas, Yun Zhao. Entropy formulas for dynamical systems with mistakes. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4391-4407. doi: 10.3934/dcds.2012.32.4391
[20]	Denis de Carvalho Braga, Luis Fernando Mello, Carmen Rocşoreanu, Mihaela Sterpu. Lyapunov coefficients for non-symmetrically coupled identical dynamical systems. Application to coupled advertising models. Discrete and Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785

2021 Impact Factor: 0.641

Tools

Metrics

Other articles
by authors

on AIMS
Kevin McGoff Ronnie Pavlov
on Google Scholar
Kevin McGoff Ronnie Pavlov

[Back to Top]