-
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
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 |
  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.
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
[Back to Top]