# Restricted Block Permutation for Two-Sample Testing

arXiv: https://arxiv.org/abs/2512.00668 · HTML: https://mlsanity.com/paper/2512.00668/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 15 references that are in the map.
- First posted on arXiv 29 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Local permutation tests for conditional independence](https://mlsanity.com/paper/2112.11666/) (2021)
- [Permutation tests using arbitrary permutation distributions](https://mlsanity.com/paper/2204.13581/) (2022)
- [Cheap Permutation Testing](https://mlsanity.com/paper/2502.07672/) (2025)
- [More Power by using Fewer Permutations](https://mlsanity.com/paper/2307.12832/) (2023)

## Abstract (arXiv)

We study a structured permutation scheme for two-sample testing that restricts permutations to single cross-swaps between block-selected representatives. Our analysis yields three main results. First, we provide an exact validity construction that applies to any fixed restricted permutation set. Second, for both the difference of sample means and the unbiased widehatMMD2 estimator, we derive closed-form one-swap increment identities whose conditional variances scale as O(h2), in contrast to the Theta(h) increment variability under full relabeling. This increment-level variance contraction sharpens the Bernstein--Freedman variance proxy and leads to substantially smaller permutation critical values. Third, we obtain explicit, data-dependent expressions for the resulting critical values and statistical power. Together, these results show that block-restricted one-swap permutations can achieve strictly higher power than classical full permutation tests while maintaining exact finite-sample validity, without relying on pessimistic worst-case Lipschitz bounds.