Importance Sampling for Estimating Exact Probabilities in Permutational Inference

This article discusses importance sampling as an alternative to conventional Monte Carlo sampling for estimating exact significance levels in a broad class of two-sample tests, including all of the linear rank tests (with or without censoring), homogeneity tests based on the chi-squared, hypergeometric, and likelihood ratio statistics, the Mantel—Haenszel trend test, and Zelen's test for a common odds ratio in several 2 × 2 contingency tables. Inference is based on randomly selecting 2 × k contingency tables from a reference set of all such tables with fixed marginals. Through a network algorithm, the tables are selected in proportion to their importance for reducing the variance of the estimated Monte Carlo p-value. Spectacular gains, up to four orders of magnitude, are achieved relative to conventional Monte Carlo sampling. The technique is illustrated on four real data sets.