A comparison of algorithms for exact analysis of unordered 2 × K contingency tables

摘要

We present a comparison of two efficient algorithms for exact analysis of an unordered 2 × K table. First, by considering conditional generating functions, we show that both the network algorithm of Mehta and Patel (J. Amer. Statist. Assoc. 78 (1983)) and the fast Fourier transform (FFT) algorithm of Baglivo et al. (J. Amer. Statist. Assoc. 82 (1992)) rest on the same foundation. This foundation is a recursive polynomial relation. We further show that the network algorithm is equivalent to a stage-wise implementation of this recursion while the FFT algorithm is based on performing the same recursion at complex roots of unity. Our empirical results for the Pearson X2, likelihood ratio, and Freeman-Halton statistics show that the network algorithm, or equivalently, the recursive polynomial multiplication algorithm is superior to the FFT algorithm with respect to computing speed and accuracy.