Martingales and descent statistics

2019/01/07 by Alperen Y. Özdemir, Özdemir, Alperen Y.
Computer Science · Mathematics · #60C05 #60F05 #60G42 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1901.01719

openalex publication_date 2019/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

This paper develops techniques to study the number of descents in random permutations via martingales. We relax an assumption in the Berry-Esseen theorem of Bolthausen (1982) to extend the theorem's scope to martingale differences of time-dependent variances. This extension leads to a new proof of the fact that the number of descents in random permutations is asymptotically normal with an error bound of order 1/√(n). The same techniques are shown to be applicable to other descent and descent-related statistics as they satisfy certain recurrence relation conditions. These statistics include inversions, descents in signed permutations, descents in Stirling permutations, the length of the longest alternating subsequences, descents in matchings and two-sided Eulerian numbers.

Related

• Sharp analysis on the joint distribution of the number of descents and inverse descents in a random permutation
• Asymptotics of descent functions
• A central limit theorem for a new statistic on permutations
• The peak and descent statistics over ballot permutations
• Variations on Descents and Inversions in Permutations