Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-11T14:53:43.430Z Has data issue: false hasContentIssue false
  • English
  • Français

Distributions of Order Patterns of Interval Maps

Published online by Cambridge University Press:  05 March 2013

AARON ABRAMS ,
ERIC BABSON ,
HENRY LANDAU ,
ZEPH LANDAU  and
JAMES POMMERSHEIM
AARON ABRAMS
Affiliation:
Washington and Lee University (e-mail: abramsa@wlu.edu)
ERIC BABSON
Affiliation:
University of California, Davis (e-mail: babson@math.ucdavis.edu)
HENRY LANDAU
Affiliation:
AT&T Research (e-mail: henryj.landau@gmail.com)
ZEPH LANDAU
Affiliation:
University of California, Berkeley (e-mail: zeph.landau@gmail.com)
JAMES POMMERSHEIM
Affiliation:
Reed College (e-mail: jamie@reed.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A permutation σ describing the relative orders of the first n iterates of a point x under a self-map f of the interval I=[0,1] is called an order pattern. For fixed f and n, measuring the points x ∈ I (according to Lebesgue measure) that generate the order pattern σ gives a probability distribution μn(f) on the set of length n permutations. We study the distributions that arise this way for various classes of functions f.

Our main results treat the class of measure-preserving functions. We obtain an exact description of the set of realizable distributions in this case: for each n this set is a union of open faces of the polytope of flows on a certain digraph, and a simple combinatorial criterion determines which faces are included. We also show that for general f, apart from an obvious compatibility condition, there is no restriction on the sequence {μn(f)}n=1,2,. . ..

In addition, we give a necessary condition for f to have finite exclusion type, that is, for there to be finitely many order patterns that generate all order patterns not realized by f. Using entropy we show that if f is piecewise continuous, piecewise monotone, and either ergodic or with points of arbitrarily high period, then f cannot have finite exclusion type. This generalizes results of S. Elizalde.

Keywords

Primary 37E05Secondary 37A0537B40
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 3 , May 2013 , pp. 319 - 341
Copyright
Copyright © Cambridge University Press 2013

References

[1]Amigó, J. M., Elizalde, S. and Kennel, M. (2008) Forbidden patterns and shift systems. J. Combin. Theory Ser. A 115 485–504.CrossRefGoogle Scholar
[2]Amigó, J. M. and Kennel, M. (2007) Topological permutation entropy. Physica D 231 137–142.CrossRefGoogle Scholar
[3]Bandt, C., Keller, G. and Pompe, B. (2002) Entropy of interval maps via permutations. Nonlinearity 15 1595–1602.CrossRefGoogle Scholar
[4]Bandt, C. and Pompe, B. (2002) Permutation entropy: A natural complexity measure for time series. Phys. Rev. Lett. 88 174102.CrossRefGoogle ScholarPubMed
[5]Elizalde, S. (2009) The number of permutations realized by a shift. SIAM J. Discrete Math. 23 765–786.CrossRefGoogle Scholar
[6]Elizalde, S. and Liu, Y. (2011) On basic forbidden patterns of functions. Discrete Appl. Math. 159 1207–1216.CrossRefGoogle Scholar
[7]Hesterberg, A. (2010) Iterated iteratedly piecewise continuous function order pattern probability distributions. Preprint.Google Scholar
[8]Misiurewicz, M. (2003) Permutations and topological entropy for interval maps. Nonlinearity 16 971–976.CrossRefGoogle Scholar
[9]Sarkovskii, O. (1964) Co-existence of cycles of a continuous mapping of a line into itself. Ukrain. Mat. Z. 16 61–71.Google Scholar
[10]Walters, P. (1982) An Introduction to Ergodic Theory, Springer.CrossRefGoogle Scholar