A Network Algorithm for Performing Fisher's Exact Test inr×cContingency Tables

Abstract

An exact test of significance of the hypothesis that the row and column effects are independent in an r × c contingency table can be executed in principle by generalizing Fisher's exact treatment of the 2 × 2 contingency table. Each table in a conditional reference set of r × c tables with fixed marginal sums is assigned a generalized hypergeometric probability. The significance level is then computed by summing the probabilities of all tables that are no larger (on the probability scale) than the observed table. However, the computational effort required to generate all r × c contingency tables with fixed marginal sums severely limits the use of Fisher's exact test. A novel technique that considerably extends the bounds of computational feasibility of the exact test is proposed here. The problem is transformed into one of identifying all paths through a directed acyclic network that equal or exceed a fixed length. Some interesting new optimization theorems are developed in the process. The numerical results reveal that for sparse contingency tables Fisher's exact test and Pearson's χ² test frequently lead to contradictory inferences concerning row and column independence.