Coherent random permutations with record statistics

Abstract

A two-parameter family of random permutations of $[n]$ is introduced, with distribution conditionally uniform given the counts of upper and lower records. The family interpolates between two versions of Ewens' distribution. A distinguished role of the family is determined by the fact that every sequence of coherent permutations $(π _n,n=1,2,\ldots)$ with the indicated kind of sufficiency is obtainable by randomisation of the parameters. Generating algorithms and asymptotic properties of the permutations follow from the representation via initial ranks.

Keywords

• random permutations
• records
• sufficiency
• ewens' distribution
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-cg] computer science [cs]/computational geometry [cs.cg]