Asymptotic Validity and Finite-Sample Properties of Approximate Randomization Tests

Abstract Randomization tests rely on simple data transformations and possess an appealing robustness property. In addition to being finite-sample valid if the data distribution is invariant under the transformation, these tests can be asymptotically valid under a suitable studentization of the test statistic, even if the invariance does not hold. However, practical implementation often encounters noisy data, resulting in approximate randomization tests that may not be as robust. In this paper, one key theoretical contribution is a non-asymptotic bound on the discrepancy between the size of an approximate randomization test and the size of the idealized randomization test using noiseless data. This allows us to derive novel conditions for the validity of approximate randomization tests under data invariances, while being able to use existing results based on studentization if the invariance does not hold. We illustrate our theory through several examples, including significance tests in linear regression. These examples clarify key aspects of how randomization tests behave in small samples and address limitations of prior theoretical results.