  We propose a general new method, the conditional permutation test, for
testing the conditional independence of variables $X$ and $Y$ given a
potentially high-dimensional random vector $Z$ that may contain confounding
factors. The proposed test permutes entries of $X$ non-uniformly, so as to
respect the existing dependence between $X$ and $Z$ and thus account for the
presence of these confounders. Like the conditional randomization test of
Cand\`es et al. (2018), our test relies on the availability of an approximation
to the distribution of $X \mid Z$. While Cand\`es et al. (2018)'s test uses
this estimate to draw new $X$ values, for our test we use this approximation to
design an appropriate non-uniform distribution on permutations of the $X$
values already seen in the true data. We provide an efficient Markov Chain
Monte Carlo sampler for the implementation of our method, and establish bounds
on the Type I error in terms of the error in the approximation of the
conditional distribution of $X\mid Z$, finding that, for the worst case test
statistic, the inflation in Type I error of the conditional permutation test is
no larger than that of the conditional randomization test. We validate these
theoretical results with experiments on simulated data and on the Capital
Bikeshare data set.
