Distributions of order patterns of interval maps
Authors:
- Aaron AbramsAAAaron Abrams
- Eric BabsonEBEric Babson
- Henry LandauHLHenry Landau
- Zeph LandauZLZeph Landau
- James PommersheimJPJames Pommersheim
Preprint
Abstract
A permutation $\sigma$ 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 \emph{order pattern}. For fixed $f$ and $n$, measuring the points $x\in I$ (according to Lebesgue measure) that generate the order pattern $\sigma$ gives a probability distribution $\mu_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 $\{\mu_n(f)\}$ for $n=1,2,...$. In addition, we give a necessary condition for $f$ to have \emph{finite exclusion type}, i.e., 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 6 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
- 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