The permutation test is one of the oldest techniques for making statistical inferences. Monte Carlo methods and asymptotic formulas have been used to approximate the associated p-values. When data are truncated, however, the permutation null distribution is difficult to handle. We describe here an efficient sequential importance sampling strategy for generating permutations with restricted positions, which provides accurate p-value approximations in all examples we have tested. A byproduct of the algorithm is to provide good estimates of permanents of zero-one matrices, which by itself is a challenging problem in computer science and applied mathematics. The key to our strategy is a connection between allowable permutations and zero-one tables with structural zeros.

KEY WORDS: Importance sampling, Markov chain Monte Carlo, Permanent, Permutation test, Zero-one table.

Please email Yuguo Chen (yuguo@stat.duke.edu) for a copy of the paper.