Abstract
A popular approach for testing if two univariate random variables are statistically independent consists of partitioning the sample space into bins, and evaluating a test statistic on the binned data. The partition size matters, and the optimal partition size is data dependent. While for detecting simple relationships coarse partitions may be best, for detecting complex relationships a great gain in power can be achieved by considering finer partitions. We suggest novel consistent distribution-free tests that are based on summation or maximization aggregation of scores over all partitions of a fixed size. We show that our test statistics based on summation can serve as good estimators of the mutual information. Moreover, we suggest regularized tests that aggregate over all partition sizes, and prove those are consistent too. We provide polynomial-time algorithms, which are critical for computing the suggested test statistics efficiently. We show that the power of the regularized tests is excellent compared to existing tests, and almost as powerful as the tests based on the optimal (yet unknown in practice) partition size, in simulations as well as on a real data example.
Introduction
Detecting statistical dependence between variables is a fundamental task in data analysis. While classical tools like Pearson’s correlation or Spearman’s $\rho$ are effective for linear or monotonic relationships, they often fail to detect complex, non-monotonic patterns such as circles, spirals, or sine waves. Modern approaches often involve partitioning the sample space into bins (similar to a 2D histogram) to identify local patterns. However, selecting the appropriate bin size presents a "Goldilocks" problem: too few bins may miss fine-grained details, while too many bins can lead to a loss of statistical power due to data sparsity. Crucially, the optimal partition size is typically unknown and data-dependent.
Methodology
The authors introduce a framework based on Data Derived Partitions (DDP) and All Derived Partitions (ADP). Instead of selecting a single "best" partition, the proposed tests aggregate scores across all possible partitions of a fixed size $m \times m$.
Aggregation and Regularization
Two primary aggregation strategies are proposed:
- Summation: This approach is robust for general dependencies and has been shown to be a consistent estimator of Mutual Information (MI).
- Maximization: This strategy is particularly effective at detecting very local or sharp differences in the data distribution.
To address the challenge of selecting the optimal partition size $m$, the authors implement a "Minimum p-value" Regularization strategy. By calculating p-values across a range of $m$ values and selecting the minimum, the test can adapt to the necessary resolution while maintaining statistical consistency.
Computational Efficiency
A significant contribution of this work is the development of polynomial-time algorithms. By iterating over cells rather than individual partitions, the authors reduce the computational complexity to $O(N^2)$ for $K$-sample problems and $O(N^4)$ for independence testing, making these tests feasible for practical use.
Results and Discussion
The effectiveness of the proposed tests was evaluated through extensive synthetic simulations and real-world data analysis.
Synthetic Simulations
The tests were applied to 13 $K$-sample setups and 14 bivariate relationship types, including complex patterns like "W" shapes, diamonds, and spirals. In these scenarios, the proposed tests demonstrated significantly higher power than classical methods (e.g., Kolmogorov-Smirnov) and modern competitors like the Maximal Information Coefficient (MIC) or Distance Correlation (dCov).
Real-World Application: Yeast Gene Expression
Using a yeast gene expression dataset containing over 6,000 genes, the researchers tested for pairwise co-dependence among 94 genes on chromosome 1. The new tests identified 3,312 significant gene-pair associations. Notably, Spearman’s correlation missed nearly 25% of these associations, and MIC missed over 90%, highlighting the prevalence of non-linear biological relationships that traditional methods overlook.
Conclusion
The proposed distribution-free tests offer a powerful and flexible framework for detecting complex dependencies. By leveraging rank-based statistics, the null distribution can be pre-calculated, facilitating high-throughput testing in fields like genomics. While the $O(N^4)$ complexity remains a challenge for extremely large datasets, the method's ability to adapt to varying resolutions and its connection to Mutual Information represent a significant advancement in non-parametric statistics.
Summary updated