Papers › independence: Fast Rank Tests
independence: Fast Rank Tests
Chaim Even-Zohar
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections