Random permutation statistics refer to the study of the probabilistic and distributional properties of real-valued functions defined on the set of all permutations of a finite set. Typically, these statistics are analyzed under the assumption that a permutation is chosen according to the uniform distribution, where each of the $n!$ possible permutations of $n$ elements has a probability of $1/n!$.
Definition and Scope
A permutation statistic is a map from the symmetric group $S_n$ to a set of numbers (usually integers or reals). When a permutation $\sigma \in S_n$ is chosen at random, the statistic becomes a random variable. Research in this field focuses on determining the expectation, variance, and limiting distribution of these variables as $n$ tends toward infinity.
Common Statistics
Several specific statistics are frequently studied due to their applications in computer science, biology, and theoretical mathematics:
- Cycles: The number of cycles in the cycle decomposition of a permutation. The number of cycles in a random permutation of $n$ elements follows a distribution that, when normalized, approaches a normal distribution as $n \to \infty$. The expected number of cycles is approximately the $n$-th harmonic number, $H_n \approx \ln n$.
- Fixed Points: The number of elements $i$ such that $\sigma(i) = i$. As $n \to \infty$, the number of fixed points in a random permutation follows a Poisson distribution with parameter $\lambda = 1$.
- Descents: A descent occurs at position $i$ if $\sigma(i) > \sigma(i+1)$. The total number of descents in a random permutation is approximately normally distributed with a mean of $(n-1)/2$.
- Inversions: A pair $(i, j)$ is an inversion if $i < j$ and $\sigma(i) > \sigma(j)$. The number of inversions is a measure of how far a permutation is from the identity. It follows a normal distribution for large $n$.
- Longest Increasing Subsequence (LIS): The length of the longest subsequence of elements in a permutation that appears in increasing order. The study of this statistic is known as Ulam's packing problem. For a random permutation of size $n$, the expected length of the LIS is asymptotically $2\sqrt{n}$, and its fluctuations follow the Tracy-Widom distribution.
Asymptotic Theory and Limit Theorems
The study of random permutation statistics often involves complex combinatorial identities and generating functions. For many statistics, as the size of the permutation set increases, the discrete distributions converge to well-known continuous distributions:
- Normal Distribution: Many additive statistics (like descents and inversions) satisfy central limit theorems.
- Poisson Distribution: Statistics related to rare events or small structures (like fixed points or cycles of a specific length) often converge to a Poisson distribution.
- Tracy-Widom Distribution: This distribution describes the law of the largest eigenvalues of random matrices and also characterizes the behavior of the longest increasing subsequence in random permutations.
Applications
Random permutation statistics are utilized in various fields:
- Algorithm Analysis: Understanding the average-case complexity of sorting algorithms (e.g., Quicksort performance is related to the number of comparisons/inversions).
- Computational Biology: Comparing genomic sequences through permutation patterns and inversion distances.
- Statistical Mechanics: Modeling physical systems where particles or states can be rearranged.
