Markov bases and subbases for bounded contingency tables. (English) Zbl 1440.62220
Summary: In this paper we study the computation of Markov bases for contingency tables whose cell entries have an upper bound. It is known that in this case one has to compute universal Gröbner bases, and this is often infeasible also in small- and medium-sized problems. Here we focus on bounded two-way contingency tables under independence model. We show that when these bounds on cells are positive the set of basic moves of all \(2\times 2\) minors connects all tables with given margins. We also give some results about bounded incomplete table and we conclude with an open problem on the necessary and sufficient condition on the set of structural zeros so that the set of basic moves of all \(2\times 2\) minors connects all incomplete contingency tables with given positive margins.
MSC:
| 62H17 | Contingency tables |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 62-08 | Computational methods for problems pertaining to statistics |
References:
| [1] | 4ti2 team (2008). 4ti2: A software package for algebraic, geometric and combinatorial problems on linear spaces. Available at http://www.4ti2.de . |
| [2] | Agresti A. (2002) Categorical data analysis (2nd ed.). Wiley, New Jersey · Zbl 1018.62002 |
| [3] | Aoki S., Takemura A. (2005) Markov chain Monte Carlo exact tests for incomplete two-way contingency table. Journal of Statistical Computation and Simulation 75(10): 787–812 · Zbl 1076.62060 · doi:10.1080/00949650410001690079 |
| [4] | Aoki S., Takemura A. (2008) The largest group of invariance for Markov bases and toric ideals. Journal of Symbolic Computation 43(5): 342–358 · Zbl 1143.14042 · doi:10.1016/j.jsc.2007.11.002 |
| [5] | Aoki S., Takemura A. (2010) Markov chain Monte Carlo tests for designed experiments. Journal of Statistical Planning and Inference 140(3): 817–830 · Zbl 1177.62097 · doi:10.1016/j.jspi.2009.09.010 |
| [6] | Bigatti A., La Scala R., Robbiano L. (1999) Computing toric ideals. Journal of Symbolic Computation 27(4): 351–365 · Zbl 0958.13009 · doi:10.1006/jsco.1998.0256 |
| [7] | Chen, Y., Dinwoodie, I., Dobra, A., Huber, M. (2005). Lattice points, contingency tables, and sampling. In Integer points in polyhedra: Geometry, number theory, algebra, optimization. Contemporary mathematics (Vol. 374, pp. 65–78). Providence: American Mathematical Society · Zbl 1073.62051 |
| [8] | Chen Y., Dinwoodie I.H., Sullivant S. (2006) Sequential importance sampling for multiway tables. The Annals of Statistics 34(1): 523–545 · Zbl 1091.62051 · doi:10.1214/009053605000000822 |
| [9] | Chen Y., Dinwoodie I.H., Yoshida R. (2010) Markov chains, quotient ideals and connectivity with positive margins. In: Gibilisco P., Riccomagno E., Rogantin M.P., Wynn H.P. (eds) Algebraic and geometric methods in statistics. Cambridge University Press, New York, pp 99–110 |
| [10] | CoCoATeam (2007). CoCoA: A system for doing computations in commutative algebra. Available at http://cocoa.dima.unige.it . |
| [11] | Cox D., Little J., O’Shea D. (1992) Ideals, varieties, and algorithms. Springer, New York |
| [12] | Cryan, M., Dyer, M., Randall, D. (2005). Approximately counting integral flows and cell-bounded contingency tables. In Proceedings of the thirty-seventh annual ACM symposium on theory of computing (pp. 413–422), Baltimore, MD. · Zbl 1192.68887 |
| [13] | De Loera J., Onn S. (2005) Markov bases of three-way tables are arbitrarily complicated. Journal of Symbolic Computation 41(2): 173–181 · Zbl 1120.62043 · doi:10.1016/j.jsc.2005.04.010 |
| [14] | Diaconis P., Sturmfels B. (1998) Algebraic algorithms for sampling from conditional distributions. The Annals of Statistics 26(1): 363–397 · Zbl 0952.62088 · doi:10.1214/aos/1030563990 |
| [15] | Greuel, G.-M., Pfister, G., Schönemann, H. (2009). Singular 3.1.0: A computer algebra system for polynomial computations. http://www.singular.uni-kl.de . · Zbl 1344.13002 |
| [16] | Hara, H., Takemura, A., Yoshida, R. (2010). On connectivity of fibers with positive marginals in multiple logistic regression. Journal of Multivariate Analysis, in press. · Zbl 1181.62108 |
| [17] | Pistone, G., Riccomagno, E., Wynn, H. P. (2001). Algebraic statistics: Computational commutative algebra in statistics. Boca Raton: Chapman and Hall/CRC. · Zbl 0960.62003 |
| [18] | Rapallo F. (2006) Markov bases and structural zeros. Journal of Symbolic Computation 41(2): 164–172 · Zbl 1120.62044 · doi:10.1016/j.jsc.2005.04.002 |
| [19] | Rapallo, F., Rogantin, M. P. (2007). Markov chains on the reference set of contingency tables with upper bounds. Metron, 65(1). · Zbl 1202.62077 |
| [20] | Shao J. (1998) Mathematical statistics. Springer, New York |
| [21] | Sturmfels, B. (1996). Gröbner bases and convex polytopes. University lecture series (Vol. 8). Providence: American Mathematical Society. · Zbl 0856.13020 |
| [22] | Sturmfels, B. (2002). Solving systems of polynomial equations. CBMS regional conference series in mathematics (Vol. 97). Washington, DC: Conference Board of the Mathematical Sciences. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
