Record‐dependent measures on the symmetric groups1. Issue 4 (5th March 2014)

• Record Type: Journal Article
• Authors: Gnedin, Alexander; Gorin, Vadim
• Is Part Of: Random structures & algorithms. Volume 46:Issue 4(2015)
• Page Start: 688
• Page End: 706
• Publication Date: 2014-03-05
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20526
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <sec id="rsa20526-sec-0001" sec-type="section"> <p>A probability measure <italic>P<sub>n</sub></italic> on the symmetric group <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2mv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20526:rsa20526-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi mathvariant="fraktur">S</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> is said to be record‐dependent if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2kb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20526:rsa20526-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>P</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>σ</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> depends only on the set of records of a permutation <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2pw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20526:rsa20526-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>σ</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi mathvariant="fraktur">S</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>. A sequence <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7k2nc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20526:rsa20526-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>P</mml:mi><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>P</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>∈</mml:mo><mml:mo>ℕ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> of consistent record‐dependent measures determines a random order on ℕ. In this paper we describe the extreme elements of the convex set of such <italic>P</italic>. 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</p> </sec> </abstract>