DISTRIBUTIONS OF ORDER PATTERNS OF INTERVAL MAPS

Abstract. A permutation σ describing the relative orders of the first n iter-ates 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, 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. Given a function f: [0, 1] → [0, 1], it is natural to examine properties of the sequence of iterates of f beginning at some point x ∈ [0, 1]: x, f(x), f2(x).... The order pattern for a sequence of distinct reals y1, y2,..., yn is the permutation σ ∈ Sn that ranks the elements in increasing order; specifically, yi < yj if and only if σ(i) < σ(j). A number of authors have explored the relationship between functions f and the set of order patterns realized by the iterates of f. Work o