Counting Small Permutation Patterns
arXiv:1911.01414 · doi:10.1137/1.9781611976465.136
Abstract
A sample of n generic points in the xy-plane defines a permutation that relates their ranks along the two axes. Every subset of k points similarly defines a pattern, which occurs in that permutation. The number of occurrences of small patterns in a large permutation arises in many areas, including nonparametric statistics. It is therefore desirable to count them more efficiently than the straightforward ~O(n^k) time algorithm. This work proposes new algorithms for counting patterns. We show that all patterns of order 2 and 3, as well as eight patterns of order 4, can be counted in nearly linear time. To that end, we develop an algebraic framework that we call corner tree formulas. Our approach generalizes the existing methods and allows a systematic study of their scope. Using the machinery of corner trees, we find twenty-three independent linear combinations of order-4 patterns, that can be computed in time ~O(n). We also describe an algorithm that counts one of the remaining 4-patterns, and hence all 4-patterns, in time ~O(n^(3/2)). As a practical application, we provide a nearly linear time computation of a statistic by Yanagimoto (1970), Bergsma and Dassios (2010). This statistic yields a natural and strongly consistent variant of Hoeffding's test for independence of X and Y, given a random sample as above. This improves upon the so far most efficient ~O(n^2) algorithm.
References in corpus (13)
- A consistent multivariate test of association based on ranks of distances
- A consistent test of independence based on a sign covariance related to Kendall's tau
- Consistent distribution-free -sample and independence tests for univariate random variables
- Minimum number of monotone subsequences of length 4 in permutations
- Nonparametric testing of conditional independence by means of the partial copula
- The copies of any permutation pattern are asymptotically normal
- The computational landscape of permutation patterns
- A Central Limit Theorem for Vincular Permutation Patterns
- Computing the Bergsma Dassios sign-covariance
- Improving bounds on packing densities of 4-point permutations
- On Three Different Notions of Monotone Subsequences
- High dimensional consistent independence testing with maxima of rank correlations
- Faster and simpler algorithms for finding large patterns in permutations