Restricted Block Permutation for Two-Sample Testing
Jungwoo Ho · 2025
Read Restricted Block Permutation for Two-Sample Testing by Jungwoo Ho (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00668.txt.
Introduction
Two-sample tests ask whether two groups come from the same distribution, and permutation tests answer by shuffling labels. Jungwoo Ho studies a restricted block permutation scheme for such testing in 2025. Permutations are limited to single cross-swaps between block-selected representatives.
The analysis yields three main results, beginning with an exact validity construction that applies to any fixed restricted permutation set. Restricting permutations slashes computation, which matters for huge modern datasets. Proving validity anyway keeps the statistical guarantee intact, so speed does not come at the price of untrustworthy p-values. Blocks keep related observations together, respecting structure that naive shuffling would destroy. Exact validity means the test's error rates are what they claim to be.
Catalog record
| CREATOR | Jungwoo Ho |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00668
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Restricted Block Permutation for Two-Sample Testing Jungwoo Ho Abstract 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 MMD ^ 2 \widehat{\mathrm{MMD}}^{2} estimator, we derive closed-form one-swap increment identities whose conditional variances scale as O ( h 2 ) O(h^{2}) , in contrast to the Θ ( h ) \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. 1 Introduction Permutation tests serve as a cornerstone of nonparametric inference, providing exact control of the type-I error rate in finite samples without distributional assumptions ( 9 , 6 , 15 , 12 , 8 ) . Their robustness and flexibility have made them widely used in modern statistical methodologies, including two-sample testing via the Maximum Mean Discrepancy (MMD) and independence testing via the Hilbert–Schmidt Independence Criterion (HSIC). Classical theory implicitly assumes that using the full symmetric group \mathcal{S}_{N} , or a large Monte Carlo sample drawn uniformly from it, yields the most powerful test. A long-standing intuition is that restricting the permutation space inevitably sacrifices power because fewer label rearrangements should provide less information. However, recent work challenges this paradigm. 11 demonstrate that strategically chosen representative subgroups of \mathcal{S}_{N} can paradoxically increase statistical power. The key mechanism is that restricted permutations may reduce the variability of the permutation reference distribution under the null while preserving the statistic’s magnitude under the alternative. Earlier foundational work on restricted randomization ( 2 , 8 , 3 ) similarly shows that exact testing is possible even under strong structural constraints. In parallel, structured or “local” permutations have been investigated for different objectives. 10 introduced locally constrained permutations for conditional independence testing, establishing minimax optimality under smoothness constraints, while 5 proposed grouping-based “cheap” permutations to reduce computational cost. Although such approaches demonstrate clear benefits of structured permutation strategies, they do not explicitly analyze or optimize the variability of permutation increments , which ultimately determines the tail behavior and critical values in standard two-sample testing. Our perspective. This work develops a principled analysis of a particular form of structural restriction— block-restricted one-swap permutations —in which the data are partitioned into blocks and only single cross-swaps between block representatives are permitted. Despite being a tiny combinatorial fraction of \mathcal{S}_{N} , this construction preserves exact finite-sample validity via the generalized randomization framework of 14 and classical results on restricted permutation sampling ( 2 , 8 ) . A key insight is that the induced permutation trajectory \sigma_{0}\to\sigma_{1}\to\cdots\to\sigma_{L} has tightly controlled increments. Specifically, the statistic differences \Delta_{t}:=T(\sigma_{t})-T(\sigma_{t-1}) form a bounded martingale difference sequence , a structural property not present in full relabeling. This formulation enables the direct application of Bernstein–Freedman inequalities ( 7 ) , yielding sharp, data-dependent tail bounds without relying on worst-case Lipschitz constants ( 13 , 1 ) . Most importantly, for canonical two-sample statistics such as the difference in sample means and the unbiased MMD 2 , we obtain closed-form one-swap increment identities whose conditional variances scale as \mathrm{Var}(\Delta_{t})=O(h^{2}), where h=\tfrac{1}{n_{1}}+\tfrac{1}{n_{2}} denotes the effective two-sample resolution. In contrast, the full relabeling scheme exhibits increment-level variability of order \Theta(h) . This increment-level variance contraction directly sharpens the Bernstein–Freedman variance proxy and leads to substantially smaller permutation critical values and reduced minimum detectable effects (MDE). As a consequence, the resulting test achieves strictly higher power than the classical permutation test while maintaining exact finite-sample validity. Contributions. Our main theoretical contributions are as follows: • Exact validity under restricted permutations. Leveraging the framework of 14 together with classical restricted randomization results ( 6 , 15 , 2 , 8 ) , we show that uniform sampling over our block-restricted one-swap permutation set preserves exact finite-sample type-I error control. • Martingale formulation of swap increments. We prove that the statistic increments along any admissible swap path form a bounded martingale difference sequence. This structure enables the use of Bernstein–Freedman inequalities ( 7 ) to derive sharp, data-dependent tail bounds without relying on global Lipschitz constants ( 13 , 1 ) . • Increment-level variance contraction. For the two-sample mean difference and the unbiased MMD 2 , we establish closed-form expressions for one-swap increments whose variances scale as O(h^{2}) , compared to \Theta(h) for full relabeling. This contraction of the Bernstein–Freedman variance proxy yields smaller critical values, reduced MDE, and strictly improved statistical power. The rest of the paper is organized as follows. Section 2 formalizes the two-sample framework and the block-restricted one-swap construction, and recalls a general validity result for arbitrary restricted permutation sets. Section 3 develops a Bernstein–Freedman concentration bound along restricted swap paths. Section 4 computes exact one-swap variance identities for canonical two-sample statistics. Section 5 translates these variance contractions into explicit bounds on critical values and power. Section 6 discusses practical design choices for blocks, representatives, and pairing. Section 7 presents empirical results. We conclude with a discussion of open design questions in Section 7. 2 Setup and Block–Restricted One-Swap Construction In this section we formalize the two-sample setup, introduce the block–restricted one-swap scheme, and recall a general validity result for arbitrary restricted permutation sets. 2.1 Two-sample framework and notation We observe two samples A=\{X_{1},\dots,X_{n_{1}}\},\qquad B=\{Y_{1},\dots,Y_{n_{2}}\}, drawn from a common measurable space \mathcal{X} . Let N=n_{1}+n_{2} and define the pooled sample Z=(Z_{1},\dots,Z_{N}) together with the group labels g=(g_{1},\dots,g_{N})\in\{A,B\}^{N} . A generic permutation \sigma\in S_{N} acts on the indices so that Z_{\sigma}=(Z_{\sigma(1)},\dots,Z_{\sigma(N)}) and g_{\sigma} is the induced label vector. A predetermined test statistic T(\sigma) is computed on Z_{\sigma} ; throughout we assume that larger values of T(\sigma) indicate stronger evidence against the null. We consider the classical two-sample null hypothesis H_{0}:\mathcal{L}(X_{1})=\mathcal{L}(Y_{1}), possibly in a multivariate setting, and focus on two canonical statistics: the difference in sample means and the unbiased two-sample \widehat{\mathrm{MMD}}^{2} . We also define the effective two-sample resolution h:=\frac{1}{n_{1}}+\frac{1}{n_{2}}. (1) 2.2 Block partition and representative ratio Let \{1,\dots,N\} denote the pooled index set. We partition it into b disjoint blocks \mathcal{B}_{1},\dots,\mathcal{B}_{b},\qquad\mathcal{B}_{r}\cap\mathcal{B}_{s}=\emptyset,\quad\bigcup_{r=1}^{b}\mathcal{B}_{r}=\{1,\dots,N\}, using a label-independent similarity rule (e.g., covariates, prognostic scores, or kernel-based scores). From these blocks we select a global representative set R\subseteq\{1,\dots,N\} of size |R|=\big\lfloor\rho\,N\big\rfloor,\qquad\rho\in(0,1], for instance by assigning per-block quotas proportional to |\mathcal{B}_{r}| and taking the union. We then define the set of admissible ordered cross-swaps \mathcal{P}:=\{(i,j):i\in A\cap R\cap\mathcal{B}_{r},\;j\in B\cap R\cap\mathcal{B}_{s},\;r\neq s\}, (2) where each (i,j)\in\mathcal{P} represents a cross-swap between distinct blocks r and s . Let w=\{w_{ij}\}_{(i,j)\in\mathcal{P}} denote a sampling law on \mathcal{P} ; throughout we take w to be uniform: w_{ij}=\frac{1}{|\mathcal{P}|},\qquad(i,j)\in\mathcal{P}, so that a random swap (I,J)\sim w is drawn uniformly among all admissible cross-swaps. Expectations and variances with respect to this swap law (conditional on the data) are denoted by \mathbb{E}_{w}[\cdot] and \mathrm{Var}_{w}(\cdot) . A block–restricted one-swap permutation is obtained by applying a finite sequence of disjoint cross-swaps from \mathcal{P}