Sequential Monte Carlo Methods for Statistical Analysis of Tables

Yuguo Chen, Persi Diaconis, Susan Holmes, Jun S. Liu

TL;DR

This paper introduces a novel Sequential Importance Sampling (SIS) method for efficiently analyzing zero-one and contingency tables with fixed marginal sums. The approach significantly outperforms existing methods, particularly Markov Chain Monte Carlo (MCMC), in both speed and accuracy for tasks like estimating the total number of such tables and approximating null distributions of test statistics.

What Problem Does This Paper Address?

Researchers in fields like ecology, statistics, and biology often encounter datasets that can be represented as zero-one matrices (e.g., species presence/absence across locations) or general contingency tables. A fundamental statistical problem is to understand the distribution of these tables under a null hypothesis, typically assuming they are drawn uniformly from all tables with the same row and column sums (marginal sums). This is crucial for hypothesis testing, where we compare an observed table to this null distribution.

However, precisely counting the total number of such tables or accurately approximating the null distributions of test statistics is computationally very challenging. Existing methods, especially Markov Chain Monte Carlo (MCMC), struggle with efficiency, mixing issues (ensuring the chain explores the entire sample space), and accurately estimating the total count of tables. This paper aims to provide a more efficient and robust solution.

Methods

The core of the paper is a Sequential Importance Sampling (SIS) procedure. Instead of generating entire tables at once, SIS builds tables column by column. At each step, it samples a column based on a "proposal distribution" that is designed to be close to the true target distribution (uniform distribution over valid tables). The key innovations are:

  • Column-by-Column Sampling: This sequential approach allows for a more structured generation process.
  • Conditional-Poisson (CP) Sampling: For zero-one tables, the paper leverages CP sampling, which uses weights proportional to row sums to guide the placement of '1's. This is a significant improvement over naive uniform sampling within columns.
  • "Delicate" SIS: A refined version of the SIS method is introduced that includes a check for the existence of valid subtables at each step. This guarantees that the generated table will always be valid, preventing wasted computation and ensuring the proposal distribution's support matches the target distribution's support.
  • Contingency Table Sampling: A simpler SIS approach is presented for general contingency tables, leveraging the fact that their existence is less constrained than zero-one tables.

The method estimates quantities of interest (like p-values or table counts) using weighted averages of samples drawn from the proposal distribution. The efficiency is measured by the coefficient of variation (CV) of the importance weights.

Datasets

The paper uses several datasets for evaluation:

  • Darwin's Finch Data: A classic 13x17 zero-one occurrence matrix used to illustrate ecological competition hypotheses.
  • Synthetic Zero-One Tables: Various sizes (e.g., 12x12, 50x50, 100x100) with specified marginal sums, including cases with uniform sums and cases with highly varying sums, to test counting and hypothesis testing capabilities.
  • Land Bird Occurrence Data: A dataset from Cody (1983) to compare SIS with MCMC on a real ecological problem.
  • Rasch Model Data: A 100x6 zero-one matrix used to test item bias in educational testing.
  • Contingency Tables: Two examples from Diaconis and Gangolli (1995) (a 5x3 table and a 4x4 table) to demonstrate counting and hypothesis testing for contingency tables.

Key Insights and Ideas

  • Sequential Generation is Key: Building tables column by column, and using the partially built table to inform the next step, is a powerful strategy for managing the complexity of fixed marginal constraints.
  • CP Sampling for Zero-One Tables: The use of Conditional-Poisson sampling, with weights derived from row sums, dramatically improves the efficiency of sampling zero-one tables compared to naive methods.
  • Guaranteed Validity: The "delicate" SIS method's ability to ensure that every generated table is valid is crucial for practical efficiency and theoretical correctness.
  • SIS Outperforms MCMC: The paper consistently shows that SIS is significantly faster and more accurate than MCMC for the tasks considered, especially for larger tables. This is attributed to SIS avoiding the "mixing" problems inherent in MCMC.
  • Efficient Table Counting: SIS provides a robust and accurate way to estimate the total number of tables with fixed marginal sums, a problem notoriously difficult for MCMC.

Key Results

  • Efficiency Gains: The SIS method is shown to be "a few orders of magnitude more efficient" than MCMC in many cases, with speedups of up to 1,600 times observed for certain problems.
  • Accuracy: SIS provides highly accurate estimates for table counts and p-values, often matching or exceeding the accuracy of MCMC with far fewer samples. For example, estimating the number of finch data tables yielded a cv² of around 1, and a 50x50 table estimation had a cv² of .03.
  • P-value Estimation: For the finch data, SIS estimated a p-value of (4±2.8) × 10⁻⁴, providing strong evidence against the null hypothesis.
  • Table Counting: For the 12x12 zero-one tables with marginal sums of 2, SIS estimated the count to be (2.196±.004) × 10¹⁶, very close to the exact value. For the finch data, it estimated (6.72 ± .07) × 10¹⁶ tables.

Limitations and Future Work

  • Ordering Heuristics: While the paper suggests heuristic rules for ordering row and column sums to minimize CV² (e.g., ordering column sums from largest to smallest for zero-one tables), finding the optimal ordering can still be a challenge.
  • Weight Adjustment: The paper mentions that the CP sampling weights can be further adjusted (e.g., by raising them to a power u) to potentially improve efficiency, but notes that u=1 (standard CP) worked well in their tests. Further exploration of optimal weight adjustments could be a future direction.
  • Generalization: While the paper covers zero-one and general contingency tables, extending the "delicate" SIS to more complex table structures or constraints might be an area for future research.

The authors conclude that their SIS approach offers a powerful, efficient, and conceptually simpler alternative to existing methods for statistical analysis of tables, particularly for problems involving exact tests and combinatorial counting.

Summary updated

Abstract

We describe a sequential importance sampling (SIS) procedure for analyzing two-way zero–one or contingency tables with fixed marginal sums. An essential feature of the new method is that it samples the columns of the table progressively according to certain special distributions. Our method produces Monte Carlo samples that are remarkably close to the uniform distribution, enabling one to approximate closely the null distributions of various test statistics about these tables. Our method compares favorably with other existing Monte Carlo-based algorithms, and sometimes is a few orders of magnitude more efficient. In particular, compared with Markov chain Monte Carlo (MCMC)-based approaches, our importance sampling method not only is more efficient in terms of absolute running time and frees one from pondering over the mixing issue, but also provides an easy and accurate estimate of the total number of tables with fixed marginal sums, which is far more difficult for an MCMC method to achieve.
BibTeX
@article{chen2005sequential,
  author = {Yuguo Chen and Persi Diaconis and Susan Holmes and Jun S. Liu},
  title = {{Sequential Monte Carlo Methods for Statistical Analysis of Tables}},
  journal = {Journal of the American Statistical Association},
  year = {2005},
  doi = {10.1198/016214504000001303},
}
Figure