  Generalizations to the permutation test are introduced to allow for
situations in which the null model is not exchangeable. It is shown that the
generalized permutation tests are exact, and a partial converse: that any test
function that is exact on all probability densities coincides with a
generalized permutation test on a particular region, is established. A most
powerful generalized permutation test is derived in closed form. Approximations
to the most powerful generalized permutation test are proposed to reduce the
computational burden required to compute the complete test. In particular, an
explicit form for the approximate test is derived in terms of a multinomial
Bernstein polynomial approximation, and its convergence to the most powerful
generalized permutation test is demonstrated. In the case where the
determination of p-values is of greater interest than testing of hypotheses,
two approaches to estimation of significance are analyzed. Bounds on the
deviation from significance of the exact most powerful test are given in terms
of sample size. For both estimators, as sample size approaches infinity, the
estimator converges to the significance of the most powerful generalized
permutation test under mild conditions. Applications of generalized permutation
testing to linear mixed models are provided.
