Sequential Monte Carlo methods for permutation tests on truncated data

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. The algorithm also provides good estimates of permanents of zero-one matrices, which by itself is a challenging problem. The key to our strategy is a connection between allowable permutations and zero-one tables with structural zeros.