American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66 (1966), 72pp.  Google Scholar

[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.  Google Scholar

[7]

M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory and Dynamical Systems, 3 (1983), 541-557. doi: 10.1017/S0143385700002133.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

W. Krieger, On the subsystems of topological Markov chains, Ergodic Theory and Dynamical Systems, 2 (1982), 195-202. doi: 10.1017/S0143385700001516.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.  Google Scholar

[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.  Google Scholar

[25]

B. Marcus, Factors and extensions of full shifts, Monatsh. Math., 88 (1979), 239-247. doi: 10.1007/BF01295238.  Google Scholar

[26]

K. McGoff, Random subshifts of finite type, Ann. Probab., 40 (2012), 648-694. doi: 10.1214/10-AOP636.  Google Scholar

[27]

M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math., 60 (1938), 815-866. doi: 10.2307/2371264.  Google Scholar

[28]

W. Parry, Intrinsic Markov chains, Trans. Amer. Math. Soc., 112 (1964), 55-66. doi: 10.1090/S0002-9947-1964-0161372-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66 (1966), 72pp.  Google Scholar

[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.  Google Scholar

[7]

M. Boyle, Lower entropy factors of sofic systems, Ergodic Theory and Dynamical Systems, 3 (1983), 541-557. doi: 10.1017/S0143385700002133.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

W. Krieger, On the subsystems of topological Markov chains, Ergodic Theory and Dynamical Systems, 2 (1982), 195-202. doi: 10.1017/S0143385700001516.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.  Google Scholar

[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.  Google Scholar

[25]

B. Marcus, Factors and extensions of full shifts, Monatsh. Math., 88 (1979), 239-247. doi: 10.1007/BF01295238.  Google Scholar

[26]

K. McGoff, Random subshifts of finite type, Ann. Probab., 40 (2012), 648-694. doi: 10.1214/10-AOP636.  Google Scholar

[27]

M. Morse and G. A. Hedlund, Symbolic Dynamics, Amer. J. Math., 60 (1938), 815-866. doi: 10.2307/2371264.  Google Scholar

[28]

W. Parry, Intrinsic Markov chains, Trans. Amer. Math. Soc., 112 (1964), 55-66. doi: 10.1090/S0002-9947-1964-0161372-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete & 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 & 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 & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021143
[4]

Yujun Zhu. Preimage entropy for random dynamical systems. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2020, 40 (1) : 81-105. doi: 10.3934/dcds.2020004
[16]

Alfredo Marzocchi, Sara Zandonella Necca. Attractors for dynamical systems in topological spaces. Discrete & Continuous Dynamical Systems, 2002, 8 (3) : 585-597. doi: 10.3934/dcds.2002.8.585
[17]

David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287
[18]

Philipp Gohlke, Dan Rust, Timo Spindeler. Shifts of finite type and random substitutions. Discrete & 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 & 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 & Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785

2020 Impact Factor: 0.848

Tools

Metrics

  • PDF downloads (99)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy