2023/02/20 by Tobias Müller, Fiona Skerman, Muller, Tobias +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2302.10148
openalex publication_date 2023/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A random permutation Πn of \1,…,n\ follows the \DeclareMathOperator\MallowsMallows\Mallows(n,q) distribution with parameter q>0 if ℙ ( Πn = π) is proportional to \DeclareMathOperator\invinv q\inv(π) for all π. Here \DeclareMathOperator\invinv \inv(π) := |\ i π(j) \| denotes the number of inversions of π. We consider properties of permutations that can be expressed by the sentences of two different logical languages. Namely, the theory of one bijection (TOOB), which describes permutations via a single binary relation, and the theory of two orders (TOTO), where we describe permutations by two total orders. We say that the convergence law holds with respect to one of these languages if, for every sentence ϕ in the language, the probability ℙ (Πn satisfies ϕ) converges to a limit as n→∞. If moreover that limit is in the set \0,1\ for all sentences, then the zero-one law holds. We will show that with respect to TOOB the \Mallows(n,q) distribution satisfies the zero-one law when 01 the convergence law fails. (In the case when q=1 Compton has shown the convergence law holds but not the zero-one law.) We will prove that with respect to TOTO the \Mallows(n,q) distribution satisfies the convergence law but not the zero-one law for any fixed q≠ 1, and that if q=q(n) satisfies 1 - 1/log^*n < q < 1 + 1/log^*n then \Mallows(n,q) fails the convergence law. Here log^* denotes the discrete inverse of the tower function.