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

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

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.
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. 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. 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. 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. doi: 10.1090/S0894-0347-04-00464-3.

[5]

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

[6]

R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms,, Second revised edition, (2008).

[7]

M. Boyle, Lower entropy factors of sofic systems,, Ergodic Theory and Dynamical Systems, 3 (1983), 541. 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. 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. doi: 10.1017/S0143385700007859.

[10]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces,, Lecture Notes in Mathematics, (1976).

[11]

N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions,, Proc. Amer. Math. Soc., 16 (1965), 109. 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, 12 (1999), 1017. doi: 10.1090/S0894-0347-99-00305-7.

[13]

G. Grimmett, Percolation,, Second edition, (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. 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. doi: 10.4007/annals.2010.171.2011.

[16]

M. S. Keane, Ergodic theory and subshifts of finite type,, in Ergodic Theory, (1989), 35.

[17]

B. Kitchens, Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts,, Universitext, (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. 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. 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. 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. doi: 10.1017/S0143385704000276.

[22]

D. Lind, A zeta function for $\mathbbZ^d$-actions,, in Ergodic Theory of $\mathbbZ^d$ Actions (Warwick, (1996), 1993. doi: 10.1017/CBO9780511662812.019.

[23]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding,, Cambridge University Press, (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. doi: 10.1017/S0143385700002443.

[25]

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

[26]

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

[27]

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

[28]

W. Parry, Intrinsic Markov chains,, Trans. Amer. Math. Soc., 112 (1964), 55. 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. doi: 10.1017/S0143385702001761.

[30]

D. Ruelle, Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics,, Second edition, (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. 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. 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. 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. doi: 10.1090/S0894-0347-04-00464-3.

[5]

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

[6]

R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms,, Second revised edition, (2008).

[7]

M. Boyle, Lower entropy factors of sofic systems,, Ergodic Theory and Dynamical Systems, 3 (1983), 541. 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. 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. doi: 10.1017/S0143385700007859.

[10]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces,, Lecture Notes in Mathematics, (1976).

[11]

N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions,, Proc. Amer. Math. Soc., 16 (1965), 109. 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, 12 (1999), 1017. doi: 10.1090/S0894-0347-99-00305-7.

[13]

G. Grimmett, Percolation,, Second edition, (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. 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. doi: 10.4007/annals.2010.171.2011.

[16]

M. S. Keane, Ergodic theory and subshifts of finite type,, in Ergodic Theory, (1989), 35.

[17]

B. Kitchens, Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts,, Universitext, (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. 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. 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. 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. doi: 10.1017/S0143385704000276.

[22]

D. Lind, A zeta function for $\mathbbZ^d$-actions,, in Ergodic Theory of $\mathbbZ^d$ Actions (Warwick, (1996), 1993. doi: 10.1017/CBO9780511662812.019.

[23]

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding,, Cambridge University Press, (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. doi: 10.1017/S0143385700002443.

[25]

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

[26]

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

[27]

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

[28]

W. Parry, Intrinsic Markov chains,, Trans. Amer. Math. Soc., 112 (1964), 55. 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. doi: 10.1017/S0143385702001761.

[30]

D. Ruelle, Thermodynamic Formalism. The Mathematical Structures of Equilibrium Statistical Mechanics,, Second edition, (2004). doi: 10.1017/CBO9780511617546.

[1]

Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497

[2]

Yujun Zhu. Preimage entropy for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829

[3]

Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (7) : 3705-3717. doi: 10.3934/dcds.2016.36.3705

[4]

João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465

[5]

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

[6]

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 - A, 2013, 33 (9) : 4123-4155. doi: 10.3934/dcds.2013.33.4123

[7]

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

[8]

Lianfa He, Hongwen Zheng, Yujun Zhu. Shadowing in random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2005, 12 (2) : 355-362. doi: 10.3934/dcds.2005.12.355

[9]

Philippe Marie, Jérôme Rousseau. Recurrence for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 1-16. doi: 10.3934/dcds.2011.30.1

[10]

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

[11]

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

[12]

Jérôme Rousseau, Paulo Varandas, Yun Zhao. Entropy formulas for dynamical systems with mistakes. Discrete & Continuous Dynamical Systems - A, 2012, 32 (12) : 4391-4407. doi: 10.3934/dcds.2012.32.4391

[13]

Ji Li, Kening Lu, Peter W. Bates. Invariant foliations for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2014, 34 (9) : 3639-3666. doi: 10.3934/dcds.2014.34.3639

[14]

Weigu Li, Kening Lu. Takens theorem for random dynamical systems. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3191-3207. doi: 10.3934/dcdsb.2016093

[15]

Dou Dou. Minimal subshifts of arbitrary mean topological dimension. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1411-1424. doi: 10.3934/dcds.2017058

[16]

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

[17]

H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549

[18]

Björn Schmalfuss. Attractors for nonautonomous and random dynamical systems perturbed by impulses. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 727-744. doi: 10.3934/dcds.2003.9.727

[19]

Ivan Werner. Equilibrium states and invariant measures for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2015, 35 (3) : 1285-1326. doi: 10.3934/dcds.2015.35.1285

[20]

Weigu Li, Kening Lu. A Siegel theorem for dynamical systems under random perturbations. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 635-642. doi: 10.3934/dcdsb.2008.9.635

2016 Impact Factor: 0.706

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]