Performance of Permutation-Based U-Statistics: Validating Minimax Optimality via Simulation

Thomas M. Menino Convention & Exhibition Center 

Recent theory by Kim, Balakrishnan, and Wasserman (2022) introduces a non-asymptotic framework for the minimax power of permutation tests. This study empirically validates these theoretical guarantees for U-statistic based permutation tests through extensive simulations.

We consider two-sample testing and categorical independence testing. In the two-sample setting, we compare the Mann–Whitney U-test based on normal approximations with its permutation-based version. For independence testing, we compare the classical chi-squared test, a bootstrapped chi-squared test, and the multinomial U-statistic proposed by Kim, Balakrishnan, and Wasserman.

Our results demonstrate that while traditional tests suffer from power collapse and poor Type I error control as dimensionality increases relative to sample size, the permutation-based U-statistic consistently achieves predicted minimax separation rates. By characterizing these error rates across diverse probability distributions and real-world data, we show that permutation tests offer a practically relevant and theoretically grounded alternative for small sample testing, particularly for high-dimensional multinomial settings.

permutation tests

simulation

minimax optimality

U-statistics 

Section on Nonparametric Statistics