Comparing the inversion statistic for distribution-biased and distribution-shifted permutations with the geometric and the GEM distributions

MaRDI QIDQ5026474zbMATH OpenFDO

Authors Ross G. Pinsky

Publication date 8 February 2022

Full work available at URL https://arxiv.org/abs/2006.09260, https://alea.impa.br/articles/v19/19-09.pdf

zbMATH Keywords

\(p\)-biased\(p\)-shiftedGEM-distributioninversionMallows distributionrandom allocation modelrandom permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: For a distribution $p:={p_k}_{k=1}^{i}nfty$ on the positive integers, there are two natural ways to construct a random permutation in $S_n$ or of $mathbbN$ from IID samples from $p$--the $p$-biased construction and the $p$-shifted construction. First we consider the case that $p$ is the geometric distribution with parameter $1-qin(0,1)$. In this case, the $p$-shifted random permutation has the Mallows distribution with parameter $q$. Let $P_n^{b;extGeo(1-q)}$ and $P_n^{s;extGeo(1-q)}$denote the biased and the shifted distributions on $S_n$. The expected number of inversions of a permutation under $P_n^{s;extGeo(1-q)}$ is greater than under $P_n^{b;extGeo(1-q)}$, and under either of these, a permutation tends to have many fewer inversions than it would have under the uniform distribution. For fixed $n$, both $P_n^{b;extGeo(1-q)}$ and $P_n^{s;extGeo(1-q)}$ converge weakly as $qo1$ to the uniform distribution on $S_n$. We compare the biased and the shifted distributions by studying the inversion statistic under $P_n^{b;extGeo(q_n)}$ and $P_n^{s;extGeo(q_n)}$ for various rates of convergence of $q_n$ to 1. Then we consider $p$-biased and $p$-shifted permutations in the case that the distribution $p$ is itself random and distributed as a GEM$(heta)$-distribution. In both the GEM$(heta)$-biased and the GEM$(heta)$-shifted cases, the expected number of inversions behaves asymptotically as it does under the Geo$(1-q)$-shifted distribution with $heta=fracq1-q$. Thus, one can consider the GEM$(heta)$-shifted case as the random counterpart of the Geo$(q)$-shifted case. We also consider another $p$-biased distribution with random $p$ for which the expected number of inversions behaves asymptotically as it does under the Geo$(1-q)$-biased case with $heta$ and $q$ as above, and with $hetaoinfty$ and $qo1$.

Recommendations

• Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth
• On the number of inversions in bimodal permutations
• Coherent random permutations with biased record statistics
• Block size in geometric(\(p\))-biased permutations
• A central limit theorem for descents of a Mallows permutation and its inverse

Cites work

• Lengths of monotone subsequences in a Mallows permutation
• Limit theorems for longest monotone subsequences in random Mallows permutations
• On the cycle structure of Mallows permutations
• On the strange domain of attraction to generalized Dickman distributions for sums of independent random variables
• Regenerative random permutations of integers
• The two-sided infinite extension of the Mallows model for random permutations

Cited in

(6)

• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• The secretary problem with biased arrival order via a Mallows distribution
• The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution
• Thresholds for patterns in random permutations with a given number of inversions
• Classical patterns in Mallows permutations
• The inversion statistic in derangements and in other permutations with a prescribed number of fixed points

This page was built for publication: Comparing the inversion statistic for distribution-biased and distribution-shifted permutations with the geometric and the GEM distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026474)