Continuously Increasing Subsequences of Random Multiset Permutations

DOI10.1016/J.EJC.2023.103708MaRDI QIDQ6380814arXivFDO

Authors Alexander Clifton, Bishal Deb, Yifeng Huang, Sam Spiro, Semin Yoo

Publication date 19 October 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103708

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Probability distributions: general theory (60E05)

arXiv classification

math.COmath.PR

Abstract: For a word $pi$ and integer $i$, we define $L^i(pi)$ to be the length of the longest subsequence of the form $i(i+1)cdotsj$, and we let $L(pi):=ma{x}_i{L}^i(pi)$. In this paper we estimate the expected values of $L^1(pi)$ and $L(pi)$ when $pi$ is chosen uniformly at random from all words which use each of the first $n$ integers exactly $m$ times. We show that $mathbbE[L^1(pi)]simm$ if $n$ is sufficiently larger in terms of $m$ as $m$ tends towards infinity, confirming a conjecture of Diaconis, Graham, He, and Spiro. We also show that $mathbbE[L(pi)]$ is asymptotic to the inverse gamma function $Gamm{a}^{-1}(n)$ if $n$ is sufficiently large in terms of $m$ as $m$ tends towards infinity.

This page was built for publication: Continuously Increasing Subsequences of Random Multiset Permutations

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