  Given independent samples from P and Q, two-sample permutation tests allow
one to construct exact level tests when the null hypothesis is P=Q. On the
other hand, when comparing or testing particular parameters $\theta$ of P and
Q, such as their means or medians, permutation tests need not be level
$\alpha$, or even approximately level $\alpha$ in large samples. Under very
weak assumptions for comparing estimators, we provide a general test procedure
whereby the asymptotic validity of the permutation test holds while retaining
the exact rejection probability $\alpha$ in finite samples when the underlying
distributions are identical. The ideas are broadly applicable and special
attention is given to the k-sample problem of comparing general parameters,
whereby a permutation test is constructed which is exact level $\alpha$ under
the hypothesis of identical distributions, but has asymptotic rejection
probability $\alpha$ under the more general null hypothesis of equality of
parameters. A Monte Carlo simulation study is performed as well. A quite
general theory is possible based on a coupling construction, as well as a key
contiguity argument for the multinomial and multivariate hypergeometric
distributions.
