Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-14T01:25:09.350Z 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: [email protected])
ERIC BABSON
Affiliation:
University of California, Davis (e-mail: [email protected])
HENRY LANDAU
Affiliation:
AT&T Research (e-mail: [email protected])
ZEPH LANDAU
Affiliation:
University of California, Berkeley (e-mail: [email protected])
JAMES POMMERSHEIM
Affiliation:
Reed College (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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