Adaptive Multiscale Binary Expansion Tests for Independence

This paper introduces a new family of adaptive, distribution-free independence tests for multivariate random vectors based on binary expansion coefficients, supported by a tractable asymptotic theory. Our first key contribution establishes a general equivalence between independence testing and testing cross-covariances among exponentially many binary expansion interaction coefficients, applicable to broad sample spaces and not limited to kernel-induced representations. While this exponential interaction structure makes naive construction and computation infeasible, we overcome this challenge by reformulating the proposed tests as a class of U-statistics and deriving an explicit kernel representation that enables scalable and efficient computation. Exploiting the multiscale nature of binary expansions, the proposed framework automatically adapts to unknown dependence structures by selectively truncating higher-order interactions, yielding both strong power and clear interpretability. To further enhance power and computational efficiency, we introduce an adaptive weighted aggregation procedure, termed wa-dCoBET, which combines a baseline Covariance Binary Expansion Test (CoBET) with a distance-measure-based CoBET. Extensive simulations and a real-data application demonstrate that wa-dCoBET consistently matches or outperforms HSIC and distance covariance, particularly in higher-dimensional and non-monotone settings, while maintaining accurate type I error control. A Python implementation of the proposed procedure is available at https://github.com/yyang3388/Cobet.