Counting Small Permutation Patterns
From MaRDI portal
Publication:133306
DOI10.5555/3458064.3458200arXiv1911.01414MaRDI QIDQ133306FDOQ133306
Authors: Chaim Even-Zohar, Calvin Leng, Chaim Even-Zohar, Calvin Leng 
Publication date: 4 November 2019
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.
Full work available at URL: https://arxiv.org/abs/1911.01414
Cited In (1)
This page was built for publication: Counting Small Permutation Patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q133306)
