Statistica Sinica 17(2007), 857-872

SEQUENTIAL MONTE CARLO METHODS FOR

PERMUTATION TESTS ON TRUNCATED DATA

Yuguo Chen and Jun S. Liu

University of Illinois at Urbana-Champaign and Harvard University

Abstract: 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.

Key words and phrases: Importance sampling, Markov chain Monte Carlo, permanent, permutation test, structural zero, zero-one table.