A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

ABSTRACT

We consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows [7]. In this paper we present the first fully-polynomial randomized approximation scheme for counting contingency tables when the number of rows is constant. A novel feature of our algorithm is that it is a hybrid of an exact counting technique with an approximation algorithm, giving two distinct phases. In the first, the columns are partitioned into "small" and "large". We show that the number of contingency tables can be expressed as the weighted sum of a polynomial number of new instances of the problem, where each instance consists of some new row sums and the original large column sums. In the second phase, we show how to approximately count contingency tables when all the column sums are large. In this case, we show that the solution lies in approximating the volume of a single convex body, a problem which is known to be solvable in polynomial time [5].

REFERENCES

• 1: F. R. K. Chung , R. L. Graham , S.-T. Yau, On sampling with Markov chains, Random Structures & Algorithms, v.9 n.1-2, p.55-77, Aug./Sept. 1996
• 2: P. Diaconis and B. Efron, Testing for independence in a two-way table: new interpretations of the chi-square statistic (with discussion). Annals of Statistics, 13, 1995, pp.~845--913.
• 3: P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, in: D. Aldous, P.P. Varaiya, J. Spencer and J.M. Steele (Eds.), Discrete Probability and Algorithms, IMA Volumes on (MATH)ematics and its Applications, 72, Springer, New York, 1995, pp. 15--41.
• 4: P. Diaconis and L. Saloff-Coste, Random walk on contingency tables with fixed row and column sums. Technical Report, Department of (MATH)ematics, Harvard University, 1995.
• 5: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 6: Martin Dyer , Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science, v.246 n.1-2, p.265-278, Sept 2000 [doi>10.1016/S0304-3975(99)00136-X]
• 7: Martin Dyer , Ravi Kannan , John Mount, Sampling contingency tables, Random Structures & Algorithms, v.10 n.4, p.487-506, July 1997 [doi>10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q]
• 8: Diane Hernek, Random generation of 2 × n contingency tables, Random Structures & Algorithms, v.13 n.1, p.71-79, Aug. 1998 [doi>10.1002/(SICI)1098-2418(199808)13:1<71::AID-RSA4>3.0.CO;2-P]
• 9: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 10: J.L. Kelley and T.P. Srinivasan, Measure and Integral (Volume 1), Springer-Verlag Graduate Texts in (MATH)ematics, 116, Springer, Berlin, 1988.
• 11: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 12: R. Karp and M. Luby, Monte-Carlo algorithms for enumeration and reliability problems. in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM Press, 1983, pp. 56--64.
• 13: Ben Morris, Improved Bounds for Sampling Contingency Tables, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.121-129, August 08-11, 1999
• 14: J. Mount, Application of Convex Sampling to Optimization and Contingency Table Generation. PhD thesis, Technical report CMU-CS-95-152, Computer Science Department, Carnegie Mellon University, 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

General Terms:
Algorithms, Experimentation, Performance, Theory