Entropy on regular trees

Karl Petersen; Ibrahim Salama

doi:10.3934/dcds.2020186

Article Contents

2020, Volume 40, Issue 7: 4453-4477. Doi: 10.3934/dcds.2020186

This issue Previous Article A periodic-parabolic Droop model for two species competition in an unstirred chemostat Next Article Global well-posedness to incompressible non-inertial Qian-Sheng model

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
^* Corresponding author: Karl Petersen

Received: September 2019

Revised: December 2019

Published: April 2020

Abstract / Introduction Full Text(HTML) Figure(9) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 37B10, 37B40, 54H20.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 6. The function $ g(k) $

Download: Full-size image PowerPoint slide

Figure 7. Including half of the next row

Download: Full-size image PowerPoint slide

Figure 8. Using 5/8 of the next row

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	D. Kerr and H. Li, Ergodic Theory. Independence and Dichotomies, Springer, Cham, 2016. doi: 10.1007/978-3-319-49847-8.
[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.
[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.
[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.
[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.
[16]	R. Pavlov, Approximating the hard square entropy constant with probabilistic methods, Ann. Probab., 40 (2012), 2362-2399. doi: 10.1214/11-AOP681.
[17]	K. Petersen and I. Salama, Entropy on regular trees, preprint, arXiv: 1909.05153v1, 2019.
[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.
[19]	S. T. Piantadosi, Symbolic dynamics on free groups, Discrete Contin. Dyn. Syst., 20 (2008), 725-738. doi: 10.3934/dcds.2008.20.725.
[20]	Z. Ye and T. Berger, Information Measures for Discrete Random Fields, Science Press Beijing, Beijing, 1998.