A network Algorithm for performing Fisher's exact test in r × c contingency tables
Abstract
An exact test of significance of the hypothesis that the
row and column effects are independent in an r x c con
tingency table can be executed in principle by general
izing Fisher's exact treatment of the 2 x 2 contingency
table. Each table in a conditional reference set of r x 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 gen
erate all r x 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 x2 test frequently lead to con
tradictory inferences concerning row and column inde
pendence.
Collections
- Journal Articles [3689]