American Institute of Mathematical Sciences

Advanced
July  2020, 40(7): 4453-4477. doi: 10.3934/dcds.2020186

Entropy on regular trees

Karl Petersen 1,, and  Ibrahim Salama 2,

1. 

Department of Mathematics, CB 3250 Phillips Hall, Chapel Hill, NC 27599, USA
2. 

School of Business, North Carolina Central University, Durham, NC 27707, USA

* Corresponding author: Karl Petersen

Received  September 2019 Revised  December 2019 Published  April 2020

We show that the limit in our definition of tree shift topological entropy is actually the infimum, as is the case for both the topological and measure-theoretic entropies in the classical situation when the time parameter is $ \mathbb Z $. As a consequence, tree shift entropy becomes somewhat easier to work with. For example, the statement that the topological entropy of a tree shift defined by a one-dimensional subshift dominates the topological entropy of the latter can now be extended from shifts of finite type to arbitrary subshifts. Adapting to trees the strip method already used to approximate the hard square constant on $ \mathbb Z^2 $, we show that the entropy of the hard square tree shift on the regular $ k $-tree increases with $ k $, in contrast to the case of $ \mathbb Z^k $. We prove that the strip entropy approximations increase strictly to the entropy of the golden mean tree shift for $ k = 2,\dots,8 $ and propose that this holds for all $ k \geq 2 $. We study the dynamics of the map of the simplex that advances the vector of ratios of symbol counts as the width of the approximating strip is increased, providing a fairly complete description for the golden mean subshift on the $ k $-tree for all $ k $. This map provides an efficient numerical method for approximating the entropies of tree shifts defined by nearest neighbor restrictions. Finally, we show that counting configurations over certain other patterns besides the natural finite subtrees yields the same value of entropy for tree SFT's.

Keywords: Tree shift, complexity function, entropy.
Mathematics Subject Classification: 37B10, 37B40, 54H20.
Citation: Karl Petersen, Ibrahim Salama. Entropy on regular trees. Discrete & Continuous Dynamical Systems - A, 2020, 40 (7) : 4453-4477. doi: 10.3934/dcds.2020186
References:
[1]

N. Aubrun and M.-P. Béal, Decidability of conjugacy of tree-shifts of finite type, in Automata, Languages and Programming Part 1, Springer, Berlin, Heidelberg, 2009,132–143. doi: 10.1007/978-3-642-02927-1_13.  Google Scholar

[2]

N. Aubrun and M.-P. Béal, Sofic and almost of finite type tree-shifts, in Computer Science – Theory and Applications, Springer, Berlin, 2010, 12–24. doi: 10.1007/978-3-642-13182-0_2.  Google Scholar

[3]

N. Aubrun and M.-P. Béal, Tree-shifts of finite type, Theoret. Comput. Sci., 459 (2012), 16-25.  doi: 10.1016/j.tcs.2012.07.020.  Google Scholar

[4]

N. Aubrun and M.-P. Béal, Sofic tree-shifts, Theory Comput. Syst., 53 (2013), 621-644.  doi: 10.1007/s00224-013-9456-1.  Google Scholar

[5]

N. Aubrun and M.-P. Béal, Tree algebra of sofic tree languages, RAIRO Theor. Inform. Appl., 48 (2014), 431-451.  doi: 10.1051/ita/2014018.  Google Scholar

[6]

T. Berger and Z. X. Ye, Entropic aspects of random fields on trees, IEEE Trans. Inform. Theory, 36 (1990), 1006-1018.  doi: 10.1109/18.57200.  Google Scholar

[7]

L. P. Bowen, A brief introduction to sofic entropy theory, in Proceedings of the International Congress of Mathematicians – Rio de Janeiro 2018, Vol. 3, World Sci. Publ., Hackensack, NJ, 2019, 1847–1866, arXiv: 1711.02062v1. doi: 10.1142/9789813272880_0120.  Google Scholar

[8]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. doi: 10.1007/BFb0082364.  Google Scholar

[9]

D. Gamarnik and D. Katz, Sequential cavity method for computing free energy and surface pressure, J. Stat. Phys., 137 (2009), 205-232.  doi: 10.1007/s10955-009-9849-3.  Google Scholar

[10]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171 (2010), 2011-2038.  doi: 10.4007/annals.2010.171.2011.  Google Scholar

[11]

D. Kerr and H. Li, Ergodic Theory. Independence and Dichotomies, Springer, Cham, 2016. doi: 10.1007/978-3-319-49847-8.  Google Scholar

[12]

E. Louidor, B. Marcus and R. Pavlov, Independence entropy of $\mathbb {Z}^d$-shift spaces, Acta Appl. Math., 126 (2013), 297-317.  doi: 10.1007/s10440-013-9819-2.  Google Scholar

[13]

J. Mairesse and I. Marcovici, Uniform sampling of subshifts of finite type on grids and trees, Internat. J. Found. Comput. Sci., 28 (2017), 263-287.  doi: 10.1142/S0129054117500174.  Google Scholar

[14]

B. Marcus and R. Pavlov, Approximating entropy for a class of $\mathbb {Z}^2$ Markov random fields and pressure for a class of functions on $\mathbb {Z}^2$ shifts of finite type, Ergodic Theory Dynam. Systems, 33 (2013), 186-220.  doi: 10.1017/S0143385711000824.  Google Scholar

[15]

T. Meyerovitch and R. Pavlov, On independence and entropy for high-dimensional isotropic subshifts, Proc. Lond. Math. Soc., 109 (2014), 921-945.  doi: 10.1112/plms/pdu029.  Google Scholar

[16]

R. Pavlov, Approximating the hard square entropy constant with probabilistic methods, Ann. Probab., 40 (2012), 2362-2399.  doi: 10.1214/11-AOP681.  Google Scholar

[17]

K. Petersen and I. Salama, Entropy on regular trees, preprint, arXiv: 1909.05153v1, 2019. Google Scholar

[18]

K. Petersen and I. Salama, Tree shift topological entropy, Theoret. Comput. Sci., 743 (2018), 64-71.  doi: 10.1016/j.tcs.2018.05.034.  Google Scholar

[19]

S. T. Piantadosi, Symbolic dynamics on free groups, Discrete Contin. Dyn. Syst., 20 (2008), 725-738.  doi: 10.3934/dcds.2008.20.725.  Google Scholar

[20]

Z. Ye and T. Berger, Information Measures for Discrete Random Fields, Science Press Beijing, Beijing, 1998.  Google Scholar

show all references

References:
[1]

N. Aubrun and M.-P. Béal, Decidability of conjugacy of tree-shifts of finite type, in Automata, Languages and Programming Part 1, Springer, Berlin, Heidelberg, 2009,132–143. doi: 10.1007/978-3-642-02927-1_13.  Google Scholar

[2]

N. Aubrun and M.-P. Béal, Sofic and almost of finite type tree-shifts, in Computer Science – Theory and Applications, Springer, Berlin, 2010, 12–24. doi: 10.1007/978-3-642-13182-0_2.  Google Scholar

[3]

N. Aubrun and M.-P. Béal, Tree-shifts of finite type, Theoret. Comput. Sci., 459 (2012), 16-25.  doi: 10.1016/j.tcs.2012.07.020.  Google Scholar

[4]

N. Aubrun and M.-P. Béal, Sofic tree-shifts, Theory Comput. Syst., 53 (2013), 621-644.  doi: 10.1007/s00224-013-9456-1.  Google Scholar

[5]

N. Aubrun and M.-P. Béal, Tree algebra of sofic tree languages, RAIRO Theor. Inform. Appl., 48 (2014), 431-451.  doi: 10.1051/ita/2014018.  Google Scholar

[6]

T. Berger and Z. X. Ye, Entropic aspects of random fields on trees, IEEE Trans. Inform. Theory, 36 (1990), 1006-1018.  doi: 10.1109/18.57200.  Google Scholar

[7]

L. P. Bowen, A brief introduction to sofic entropy theory, in Proceedings of the International Congress of Mathematicians – Rio de Janeiro 2018, Vol. 3, World Sci. Publ., Hackensack, NJ, 2019, 1847–1866, arXiv: 1711.02062v1. doi: 10.1142/9789813272880_0120.  Google Scholar

[8]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. doi: 10.1007/BFb0082364.  Google Scholar

[9]

D. Gamarnik and D. Katz, Sequential cavity method for computing free energy and surface pressure, J. Stat. Phys., 137 (2009), 205-232.  doi: 10.1007/s10955-009-9849-3.  Google Scholar

[10]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171 (2010), 2011-2038.  doi: 10.4007/annals.2010.171.2011.  Google Scholar

[11]

D. Kerr and H. Li, Ergodic Theory. Independence and Dichotomies, Springer, Cham, 2016. doi: 10.1007/978-3-319-49847-8.  Google Scholar

[12]

E. Louidor, B. Marcus and R. Pavlov, Independence entropy of $\mathbb {Z}^d$-shift spaces, Acta Appl. Math., 126 (2013), 297-317.  doi: 10.1007/s10440-013-9819-2.  Google Scholar

[13]

J. Mairesse and I. Marcovici, Uniform sampling of subshifts of finite type on grids and trees, Internat. J. Found. Comput. Sci., 28 (2017), 263-287.  doi: 10.1142/S0129054117500174.  Google Scholar

[14]

B. Marcus and R. Pavlov, Approximating entropy for a class of $\mathbb {Z}^2$ Markov random fields and pressure for a class of functions on $\mathbb {Z}^2$ shifts of finite type, Ergodic Theory Dynam. Systems, 33 (2013), 186-220.  doi: 10.1017/S0143385711000824.  Google Scholar

[15]

T. Meyerovitch and R. Pavlov, On independence and entropy for high-dimensional isotropic subshifts, Proc. Lond. Math. Soc., 109 (2014), 921-945.  doi: 10.1112/plms/pdu029.  Google Scholar

[16]

R. Pavlov, Approximating the hard square entropy constant with probabilistic methods, Ann. Probab., 40 (2012), 2362-2399.  doi: 10.1214/11-AOP681.  Google Scholar

[17]

K. Petersen and I. Salama, Entropy on regular trees, preprint, arXiv: 1909.05153v1, 2019. Google Scholar

[18]

K. Petersen and I. Salama, Tree shift topological entropy, Theoret. Comput. Sci., 743 (2018), 64-71.  doi: 10.1016/j.tcs.2018.05.034.  Google Scholar

[19]

S. T. Piantadosi, Symbolic dynamics on free groups, Discrete Contin. Dyn. Syst., 20 (2008), 725-738.  doi: 10.3934/dcds.2008.20.725.  Google Scholar

[20]

Z. Ye and T. Berger, Information Measures for Discrete Random Fields, Science Press Beijing, Beijing, 1998.  Google Scholar

Figure 1.  $ \Sigma_2^{(2)} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Graph of the difference $ n_6(r) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The nonnegative polynomial $ q_k(r) $ remaining after dividing out $ p_k(r)^2 $ from $ d_k(r) $, $ k = 5 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Graph of the two terms in (76) of Prop. 1 and their difference, $ k = 5 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The interval map and its square for $ k = 7 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The function $ g(k) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Including half of the next row
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Using 5/8 of the next row
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  The graph of the fixed point equations for the golden mean
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Strip entropy estimation for $ k = 2 $
$ n $ $ B_{n-1} $ $ B_{n-1}(0) $ $ r_{n-1}(0) $ $ \log B_{n-1}/(2^n-1) $ $ \log B_{n-1}/2^n $ $ h_n^{(2)} $
$ 1 $ $ 2 $ $ 1 $ $ .5 $ $ .693 $ $ .347 $ .5025
$ 2 $ $ 5 $ $ 4 $ $ .8 $ $ .536 $ $ .402 $ .5078
$ 3 $ $ 41 $ $ 25 $ $ .6098 $ $ .531 $ $ .465 $ .50866
$ 4 $ $ 2306 $ $ 1681 $ $ .729 $ $ .516 $ $ .484 $ .50885
$ 5 $ $ 8,143,397 $ $ 5,317,636 $ $ .653 $ $ .513 $ $ .497 $ .508889
Table Options

Download as excel

$ n $ $ B_{n-1} $ $ B_{n-1}(0) $ $ r_{n-1}(0) $ $ \log B_{n-1}/(2^n-1) $ $ \log B_{n-1}/2^n $ $ h_n^{(2)} $
$ 1 $ $ 2 $ $ 1 $ $ .5 $ $ .693 $ $ .347 $ .5025
$ 2 $ $ 5 $ $ 4 $ $ .8 $ $ .536 $ $ .402 $ .5078
$ 3 $ $ 41 $ $ 25 $ $ .6098 $ $ .531 $ $ .465 $ .50866
$ 4 $ $ 2306 $ $ 1681 $ $ .729 $ $ .516 $ $ .484 $ .50885
$ 5 $ $ 8,143,397 $ $ 5,317,636 $ $ .653 $ $ .513 $ $ .497 $ .508889
[1]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012
[2]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191
[3]

Michael Schraudner. Projectional entropy and the electrical wire shift. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 333-346. doi: 10.3934/dcds.2010.26.333
[4]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385
[5]

Erik M. Bollt, Joseph D. Skufca, Stephen J . McGregor. Control entropy: A complexity measure for nonstationary signals. Mathematical Biosciences & Engineering, 2009, 6 (1) : 1-25. doi: 10.3934/mbe.2009.6.1
[6]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[7]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[8]

Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511
[9]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015
[10]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020334
[11]

Daniel Gonçalves, Marcelo Sobottka. Continuous shift commuting maps between ultragraph shift spaces. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 1033-1048. doi: 10.3934/dcds.2019043
[12]

Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036
[13]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209
[14]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[15]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299
[16]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020167
[17]

Vincent Delecroix. Divergent trajectories in the periodic wind-tree model. Journal of Modern Dynamics, 2013, 7 (1) : 1-29. doi: 10.3934/jmd.2013.7.1
[18]

Miaohua Jiang, Qiang Zhang. A coupled map lattice model of tree dispersion. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 83-101. doi: 10.3934/dcdsb.2008.9.83
[19]

Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209
[20]

Frédéric Bernicot, Bertrand Maury, Delphine Salort. A 2-adic approach of the human respiratory tree. Networks & Heterogeneous Media, 2010, 5 (3) : 405-422. doi: 10.3934/nhm.2010.5.405

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (100)
  • HTML views (77)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences