Distributions of order patterns of interval maps
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 \emph{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)} 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.
