Vi studerar längden på de längsta ökande och mest minskande subsekvenserna av slumpmässiga permutationer som dras från Mallows-måttet. Enligt denna åtgärd är sannolikheten för en permutation π  på S n proportionell mot q Inv (π) där q är en verklig parameter och Inv (π) är antalet inversioner i π. Fallet q = 1 motsvarar jämnt slumpmässiga permutationer. Mallows-åtgärden infördes av Mallows i samband med rankningsproblem i statistiken. Vi bestämmer den typiska storleksordningen av längden av de längsta ökande och minskande undersekvenserna, liksom stora avvikelsegränser för dem. Vi ger också en enkel gräns på variansen av dessa längder, och bevisa en lag av stora tal för längden av den längsta ökande subsekvensen. Om vi antar utan förlust av allmängiltighet att q < 1, våra resultat gäller när q är en funktion av n som uppfyller n(1 − q) → ∞. Fallet att n( 1 − q) = O(1) behandlades tidigare av Mueller och Starr. I vårt parameteromfång är den typiska längden av den längsta ökande subsekvensen av ordning n 1 − q, medan den typiska längden av den längsta minskande subsekvensen har fyra möjliga beteenden enligt det exakta beroendet av n och q. Vi visar också att i den grafiska representationen av en Mallows-distribuerad permutation, de flesta punkter finns i en symmetrisk remsa runt diagonalen vars bredd är av ordning 1/(1 − q). Detta tyder på ett samband mellan den längsta ökande undersekvensen i Mallows modellen och modellen för sista passagen perkolering i ett band.
Därefter, i REF, Bhatnagar och Peled etablerade den ledande ordningen beteende L n i regimen som n(1 − q) → ∞ och q → 1.
Lengths of Monotone Subsequences in a Mallows Permutation
{'venue': 'Probability Theory and Related Fields 161, no. 3-4 (2015): 719-780', 'journal': None, 'mag_field_of_study': ['Mathematics']}