A network algorithm for the exact treatment of the 2xk contingency table

Abstract

A common statistical problem encountered in biomedical research is to test the hypothesis that the parameters of k binomial populations are all equal. An exact test of significance of this hypothesis is possible in principle, the appropriate null distribution being a normalized product of k binomial coefficients. However, the problem of computing the tail area of this distribution can be formidable since it requires the enumeration of all sets of k binomial coefficients whose product is less than a given constant. Existing algorithms, all of which rely on explicit enumeration to generate feasible binomial coefficients soon become computationally infeasible. In this paper, we develop a novel technique which drastically reduces the computational effort needed to obtain the exact P-value. The problem is transformed into one of identifying feasible paths through a directed acyclic network by means of backwards induction and implicit enumeration. The technique can be generalized for the exact treatment of the RxC contingency table.