Distributions of Order Patterns of Interval Maps

作者：Abrams Aaron^*; Babson Eric; Landau Henry; Landau Zeph; Pommersheim James

来源：Combinatorics Probability & Computing, 2013, 22(3): 319-341.

DOI：10.1017/S0963548313000035

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 order pattern. For fixed f and n, measuring the points x is an element of 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)}(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.

• 出版日期2013-5