independence: Fast Rank Tests

Abstract

In 1948 Hoeffding devised a nonparametric test that detects dependence between two continuous random variables X and Y, based on the ranking of n paired samples (Xi,Yi). The computation of this commonly-used test statistic takes O(n log n) time. Hoeffding's test is consistent against any dependent probability density f(x,y), but can be fooled by other bivariate distributions with continuous margins. Variants of this test with full consistency have been considered by Blum, Kiefer, and Rosenblatt (1961), Yanagimoto (1970), Bergsma and Dassios (2010). The so far best known algorithms to compute these stronger independence tests have required quadratic time. Here we improve their run time to O(n log n), by elaborating on new methods for counting ranking patterns, from a recent paper by the author and Leng (SODA'21). Therefore, in all circumstances under which the classical Hoeffding independence test is applicable, we provide novel competitive algorithms for consistent testing against all alternatives. Our R package, independence, offers a highly optimized implementation of these rank-based tests. We demonstrate its capabilities on large-scale datasets.

References in corpus (13)

• Brownian distance covariance
• Kernel-based Conditional Independence Test and Application in Causal Discovery
• 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
• Equitability Analysis of the Maximal Information Coefficient, with Comparisons
• Comment on "Detecting Novel Associations In Large Data Sets" by Reshef Et Al, Science Dec 16, 2011
• Consistent distribution-free $K$-sample and independence tests for univariate random variables
• Multivariate Rank-based Distribution-free Nonparametric Testing using Measure Transportation
• Nonparametric testing of conditional independence by means of the partial copula
• Counting Small Permutation Patterns
• Computing the Bergsma Dassios sign-covariance
• On the power of Chatterjee rank correlation
• High dimensional consistent independence testing with maxima of rank correlations