Consistent distribution-free $K$-sample and independence tests for univariate random variables

Ruth Heller, Yair Heller, Shachar Kaufman, Barak Brill, Malka Gorfine

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:

  1. Summation: This approach is robust for general dependencies and has been shown to be a consistent estimator of Mutual Information (MI).
  2. 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.

Visualizing the construction of data-derived partitions (DDP) for different partition sizes.

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

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.
BibTeX
@article{heller2016consistent,
  author = {Ruth Heller and Yair Heller and Shachar Kaufman and Barak Brill and Malka Gorfine},
  title = {{Consistent distribution-free $K$-sample and independence tests for univariate random variables}},
  journal = {JMLR},
  year = {2016},
}
Figure