Record‐dependent measures on the symmetric groups1. Issue 4 (5th March 2014) - Gnedin, Alexander; Gorin, Vadim
<x xml:space="preserve">Abstract</x> A probability measure Pn on the symmetric group <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2mv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Sn</alternatives> is said to be record‐dependent if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2kb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Pn(σ)</alternatives> depends only on the set of records of a permutation <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2pw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />σ∈Sn</alternatives>. A sequence <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2nc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />P=(Pn)n∈ℕ</alternatives> of consistent record‐dependent measures determines a random order on ℕ. In this paper we describe the extreme elements of the convex set of such P. This problem turns out to be related to the study of asymptotic behavior of permutation‐valued growth processes, to random extensions of partial orders, and to the measures on the Young‐Fibonacci lattice. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014 © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46, 688–706, 2015