Estimating Exact p Values by the Method of Control Variates or Monte Carlo Rescue

Abstract

Despite algorithmic advances in exact nonparametric inference, problems often occur that are too large for exact p value computations but too sparse for reliable asymptotic results. In these situations Monte Carlo methods are a good compromise. They bound the true p value within a confidence interval. But a factor discouraging the use of Monte Carlo p values is their sensitivity to the random number sequence. One can overcome this drawback by computing a 99% C.I. confidence interval of width less than .0001. Then the estimated p values become insensitive to the random number sequence up to three decimals. For all practical purposes, these estimates are invariant to random number sequences. The usual Monte Carlo method requires millions of samples to yield such an invariant estimate. The Monte Carlo scheme presented here decreases the sample size by two to three orders of magnitude. We illustrate this method with tests for r × c tables, two-sample survival data, and stratified 2 × 2 tables.

Key Words:

• Exact linear rank tests
• Exact tests on contingency tables
• Network algorithms
• Simulation
• Small-sample inference
• Swindle
• Variance reduction