Distributions of Order Patterns of Interval Maps
- 5 March 2013
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (3) , 319-341
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
All Related Versions
This publication has 8 references indexed in Scilit:
- On basic forbidden patterns of functionsDiscrete Applied Mathematics, 2011
- The Number of Permutations Realized By a ShiftSIAM Journal on Discrete Mathematics, 2009
- Forbidden patterns and shift systemsJournal of Combinatorial Theory, Series A, 2008
- Topological permutation entropyPhysica D: Nonlinear Phenomena, 2007
- Permutations and topological entropy for interval mapsNonlinearity, 2003
- Entropy of interval maps via permutationsNonlinearity, 2002
- Permutation Entropy: A Natural Complexity Measure for Time SeriesPhysical Review Letters, 2002
- An Introduction to Ergodic Theory1982