Mean and variance of the longest alternating subsequence in a random separable permutation

2023/10/12 by Ross G. Pinsky, Pinsky, Ross G.
Biochemistry, Genetics and Molecular Biology · Computer Science · #05A05 #60C05 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Genomic variations and chromosomal abnormalities #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2310.08664

openalex publication_date 2023/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A permutation is \it separable \rm if it can be obtained from the singleton permutation by iterating direct sums and skew sums. Equivalently, it is separable if and only it avoids the patterns 2413 and 3142. Under the uniform probability on separable permutations of [n], let the random variable A_n denote the length of the longest alternating subsequence. Also, let A_n^+,- denote the length of the longest alternating subsequence that begins with an ascent and ends with a descent, and define A_n^-,+, A_n^+,+, A_n^-,- similarly. By symmetry, the first two and the last two of these latter four random variables are equi-distributed. We prove that the expected value of any of these five random variables behaves asymptotically as (2-√2)n≈0.5858\thinspace n. We also prove that the variance of any of the four random variables A_n^±,± behaves asymptotically as \frac16-11√22n≈0.2218\thinspace n.

Related

• On the Limiting Distribution for the Longest Alternating Sequence in a Random Permutation
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
• A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations