Continuously increasing subsequences of random multiset permutations. (May 2023) - Clifton, Alexander; Deb, Bishal; Huang, Yifeng; Spiro, Sam; Yoo, Semin
Abstract: For a word π and an integer i, we define L ( π ) to be the length of the longest subsequence of the form i ( i + 1 ) ⋯ j for some i, and we let L 1 ( π ) be the length of the longest such subsequence beginning with 1. In this paper, we estimate the expected values of L 1 ( π ) and L ( π ) when π is chosen uniformly at random from all words which use each of the first n positive integers exactly m times. We show that E [ L 1 ( π ) ] ∼ m if n is sufficiently large in terms of m as m tends towards infinity, confirming a conjecture of Diaconis, Graham, He, and Spiro. We also show that E [ L ( π ) ] is asymptotic to the inverse gamma function Γ − 1 ( n ) if n is sufficiently large in terms of m as m tends towards infinity.