Markov Bases: A 25 Year Update

References

• 4ti2 team. 4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at https://4ti2.github.io.
   Google Scholar
• Agresti, A. (2002). Categorical Data Analysis. Wiley Series in Probability and Statistics, Hoboken, NJ: Wiley.
   Google Scholar
• Andersen, E. B. (1980), Discrete Statistical Models with Social Science Applications, New York: Elsevier.
   Google Scholar
• Andersen, H. C. and Diaconis, P. (2007), “Hit and Run as a Unifying Device,” Journal de la Société française de statistique & Revue de statistique appliquée, 148, 5–28.
   Google Scholar
• Aoki, S., and Takemura, A. (2003a), “Minimal Basis for a Connected Markov Chain over 3×3×k Contingency Tables with Fixed Two-Dimensional Marginals,” Australian & New Zealand Journal of Statistics, 45, 229–249.
   Web of Science ®Google Scholar
• ———(2003b), “The List of Indispensable Moves of the Unique Minimal Markov Basis for 3×4×k and 4×4×4 Contingency Tables with Fixed Two-Dimensional Marginal.” Technical Report METR 03-38.
   Google Scholar
• Aoki, S., Takemura, A., and Yoshida, R. (2008), “Indispensable Monomials of Toric Ideals and Markov Bases,” Journal of Symbolic Computation, 43, 490–507. DOI: 10.1016/j.jsc.2007.07.012.
   Web of Science ®Google Scholar
• Aoki, S., Hara, H., and Takemura, A. (2012), Markov Bases in Algebraic Statistics, Springer Series in Statistics, New York: Springer.
   Google Scholar
• Bacallado, S., Diaconis, P., and Holmes, S. (2015), “de Finetti Priors Using Markov Chain Monte Carlo Computations,” Statistics and Computing, 25, 797–808. DOI: 10.1007/s11222-015-9562-9.
   PubMed Web of Science ®Google Scholar
• Bakenhus, M., and Petrović, S. “Sampling Lattice Points in a Polytope: A bayesian Biased Algorithm with Random Updates,” Algebraic Statistics, to appear.
   Google Scholar
• Barndorff-Nielsen, O. (1978), Information and Exponential Families: In Statistical Theory, volume Reprinted in 2014. Wiley Series in Probability and Statistics, Hoboken, NJ: Wiley.
   Google Scholar
• Bernstein, D., and O’Neill, C. (2017), “Unimodular Hierarchical Models and their Graver Bases,” Journal of Algebraic Statistics, 8, 29–43. DOI: 10.18409/jas.v8i2.66.
   Google Scholar
• Bernstein, D., and Sullivant, S. (2017), “Unimodular Binary Hierarchical Models,” Journal of Combinatorial Theory, Series B, 123, 97–125. DOI: 10.1016/j.jctb.2016.11.003.
   Web of Science ®Google Scholar
• Berstein, Y., and Onn, S. (2009), “The Graver Complexity of Integer Programming,” Annals of Combinatorics, 13, 289–296. DOI: 10.1007/s00026-009-0029-6.
   Web of Science ®Google Scholar
• Besag, J., and Clifford, P. (1989), “Generalized Monte Carlo Significance Tests,” Biometrika, 76, 633–642. DOI: 10.1093/biomet/76.4.633.
   Web of Science ®Google Scholar
• Besag, J., and Mondal, D. (2013), “Exact Goodness-of-Fit Tests for Markov Chains,” Biometrics, 69, 488–496. DOI: 10.1111/biom.12009.
   PubMed Web of Science ®Google Scholar
• Bunea, F., and Besag, J. (2000), “MCMC in i×j×k Contingency Tables,” Fields Institute Communications, 26, 1–13.
   Google Scholar
• Campo, A. M. D., Cepeda, S., and Uhler, C. (2017), “Exact Goodness-of-Fit Testing for the Ising Model,” Scandinavian Journal of Statistics, 44, 285–306. DOI: 10.1111/sjos.12251.
   Web of Science ®Google Scholar
• Chen, Y. (2007), “Conditional Inference on Tables with Structural Zeros,” Journal of Computational and Graphical Statistics, 16, 445–467. DOI: 10.1198/106186007X209226.
   Web of Science ®Google Scholar
• Chen, Y., Dinwoodie, I., and Dobra, A. (2005), “Lattice Points, Contingency Tables, and Sampling,” Contemporary Mathematics (Vol. 374), Providence, RI: American Mathematical Society.
   Google Scholar
• Cox, D. A., Little, J. B., and O’Shea, D. (2015), Ideals, Varieties, and Algorithms (4th ed.), Cham: Springer.
   Google Scholar
• Cslovjecsek, J., Eisenbrand, F., Hunkenschröder, C., Rohwedder, L., and Weismantel, R. (2021), “Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time,” in Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, pp. 1666–1681, Society for Industrial and Applied Mathematics.
   Google Scholar
• Cslovjecsek, J., Koutecký, M., Lassota, A., Pilipczuk, M., and Polak, A. (2023), “Parameterized Algorithms for Block-Structured Integer Programs with Large Entries,” to appear in SODA 2024. Available at arXiv:2311.01890.
   Google Scholar
• De Loera, J., and Onn, S. (2006a), “Markov Bases of Three-Way Tables are Arbitrarily Complicated,” Journal of Symbolic Computation, 41, 173–181. DOI: 10.1016/j.jsc.2005.04.010.
   Web of Science ®Google Scholar
• De Loera, J. A., and Onn, S. (2006b), “All Linear and Integer Programs are Slim 3-Way Transportation Programs,” SIAM Journal on Optimization, 17, 806–821. DOI: 10.1137/040610623.
   Web of Science ®Google Scholar
• De Loera, J. A., Hemmecke, R., Onn, S., and Weismantel, R. (2008), “N-fold Integer Programming,” Discrete Optimization, 5, 231–241. DOI: 10.1016/j.disopt.2006.06.006.
   Web of Science ®Google Scholar
• Diaconis, P. (2022a), “Partial Exchangeability for Contingency Tables,” Mathematics, 10, 442. DOI: 10.3390/math10030442.
   Web of Science ®Google Scholar
• ——— (2022b), “Approximate Exchangeability and De Finetti Priors in 2022,” Scandinavian Journal of Statistics, 50, 38–53.
   Web of Science ®Google Scholar
• Diaconis, P., and Eriksson, N. (2006), “Markov Bases for Noncommutative Fourier Analysis of Ranked Data,” Journal of Symbolic Computation, 41, 182–195. DOI: 10.1016/j.jsc.2005.04.009.
   Web of Science ®Google Scholar
• Diaconis, P., and Sturmfels, B. (1998), “Algebraic Algorithms for Sampling from Conditional Distributions,” Annals of Statistics, 26, 363–397.
   Web of Science ®Google Scholar
• Diaconis, P., Holmes, S., and Shahshahani, M. (2013), “Sampling from a Manifold,” Institute of Mathematical Statistics, 10, 102–125.
   Google Scholar
• Dobra, A. (2003), “Markov Bases for Decomposable Graphical Models,” Bernoulli, 9, 1093–1108. DOI: 10.3150/bj/1072215202.
   Web of Science ®Google Scholar
• ——— (2012), “Dynamic Markov Bases,” Journal of Computational and Graphical Statistics, 21, 496–517.
   Web of Science ®Google Scholar
• Dobra, A., and Sullivant, S. (2004), “A Divide-and-Conquer Algorithm for Generating Markov Bases of Multi-Way Tables,” Computational Statistics, 19, 347–366. DOI: 10.1007/BF03372101.
   Web of Science ®Google Scholar
• Dobra, A., Fienberg, S. E., Rinaldo, A., Slavković, A., and Zhou, Y. (2008), “Algebraic Statistics and Contingency Table Problems: Log-Linear Models, Likelihood Estimation and Disclosure Limitation,” in In IMA Volumes in Mathematics and its Applications: Emerging Applications of Algebraic Geometry, pp. 63–88, New York: Springer.
   Google Scholar
• Drton, M., Sturmfels, B., and Sullivant, S. (2009), Lectures on Algebraic Statistics, volume 39 of Oberwolfach Seminars, Basel: Birkhäuser.
   Google Scholar
• Eisenbrand, F., Hunkenschröder, C., Klein, K.-M., Koutecký, M., Levin, A., and Onn, S. (2022), “An Algorithmic Theory of Integer Programming,” Available at arXiv:1904.01361.
   Google Scholar
• Engström, A., Kahle, T., and Sullivant, S. (2014), “Multigraded Commutative Algebra of Graph Decompositions,” Journal of Algebraic Combinatorics, 39, 335–372. DOI: 10.1007/s10801-013-0450-0.
   Web of Science ®Google Scholar
• Fienberg, S. E. (1980), The Analysis of Cross-Classified Categorical Data, New York: Springer, Reprinted 2007.
   Google Scholar
• Fienberg, S. E., and Wasserman, S. S. (1981), “Categorical Data Analysis of Single Sociometric Relations,” Sociological Methodology, 12, 156–192. DOI: 10.2307/270741.
   Google Scholar
• Fienberg, S. E., Petrović, S., and Rinaldo, A. (2010), Algebraic Statistics for p1 Random Graph Models: Markov Bases and their Uses, volume Papers in Honor of Paul W. Holland, ETS, Springer.
   Google Scholar
• Geiger, D., Meek, C., and Sturmfels, B. (2006), “On the Toric Algebra of Graphical Models,” Annals of Statistics, 34, 1463–1492.
   Web of Science ®Google Scholar
• Goldenberg, A., Zheng, A. X., Fienberg, S. E., and Airoldi, E. M. (2010), “A Survey of Statistical Network Models,” Foundations and Trends® in Machine Learning, 2, 129–233. DOI: 10.1561/2200000005.
   Google Scholar
• Gross, E., Petrović, S., and Stasi, D. (2016), “Goodness-of-Fit for Log-Linear Network Models: Dynamic Markov Bases Using Hypergraphs,” Annals of the Institute of Statistical Mathematics, 69, 673–704. DOI: 10.1007/s10463-016-0560-2.
   Web of Science ®Google Scholar
• Gross, E., Petrović, S., and Stasi, D. (2021), “Goodness of Fit for Log-Linear ERGMs,” preprint, in revision.
   Google Scholar
• Hara, H., and Takemura, A. (2010), “Connecting Tables with Zero-One Entries by a Subset of a Markov Basis,” in Algebraic Methods in Statistics and Probability II, volume 516 of Contemporary Mathematics, eds. M. Viana and H. Wynn, 199–213, Providence, RI: American Mathematical Society.
   Google Scholar
• Hara, H., Aoki, S., and Takemura, A. (2012), “Running Markov Chain Without Markov Basis,” in Harmony of Gröbner Bases and the Modern Industrial Society, pp. 46–62, Singapore: World Scientific.
   Google Scholar
• Hazelton, M. L., Mcveagh, M. R., and van Brunt, B. (2020), “Geometrically Aware Dynamic Markov Bases for Statistical Linear Inverse Problems,” Biometrika, 108, 609–626. DOI: 10.1093/biomet/asaa083.
   Web of Science ®Google Scholar
• Hoşten, S., and Sullivant, S. (2007), “A Finiteness Theorem for Markov Bases of Hierarchical Models,” Journal of Combinatorial Theory, Series A, 114, 311–321. DOI: 10.1016/j.jcta.2006.06.001.
   Web of Science ®Google Scholar
• Kahle, D., Garcia-Puente, L., and Yoshida, R. (2014a), algstat: Algebraic Statistics in R, R package version 0.1.1. Available at https://github.com/dkahle/algstat.
   Google Scholar
• Kahle, D., Yoshida, R., and Garcia-Puente, L. (2018), “Hybrid Schemes for Exact Conditional Inference in Discrete Exponential Families,” Annals of the Institute of Statistical Mathematics, 70, 983–1011. DOI: 10.1007/s10463-017-0615-z.
   Web of Science ®Google Scholar
• Kahle, T., Rauh, J., and Sullivant, S. (2014b), “Positive Margins and Primary Decomposition,” Journal of Commutative Algebra, 6, 173–208. DOI: 10.1216/JCA-2014-6-2-173.
   Web of Science ®Google Scholar
• Karwa, V., and Petrović, S. (2016), “Coauthorship and Citation Networks for Statisticians: Comment. Invited Comment on the Paper by Jin and Ji,” Annals of Applied Statistics, 10, 1827–1834.
   Web of Science ®Google Scholar
• Karwa, V., Pati, D., Petrović, S., Solus, L., Alexeev, N., Raič, M., Wilburne, D., Williams, R., and Yan, B. (2023), “Monte Carlo Goodness-of-Fit Tests for Degree Corrected and Related Stochastic Blockmodels,” Journal of the Royal Statistical Society, Series B, to appear.
   Google Scholar
• Knop, D., Pilipczuk, M., and Wrochna, M. (2020), “Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints,” ACM Transactions on Computation Theory, 12, 1–19. DOI: 10.1145/3397484.
   Web of Science ®Google Scholar
• Kosta, D. (2020), “Markov Bases of Toric Ideals: Connecting Commutative Algebra and Statistics,” London Mathematical Society Newsletter, 486, 34–37.
   Google Scholar
• Koutecký, M., Levin, A., and Onn, S. (2018), “A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 85:1–85:14.
   Google Scholar
• Kràl, D., Norine, S., and Pangrac̀, O. (2010), “Markov Bases of Binary Graph Models of K4 -Minor Free Graphs,” Journal of Combinatorial Theory, Series A, 117, 759–765. DOI: 10.1016/j.jcta.2009.07.007.
   Web of Science ®Google Scholar
• Lauritzen, S. L. (1996). Graphical Models, Oxford Statistical Science Series, Oxford: Oxford University Press.
   Google Scholar
• Lee, S. (2018), “Markov Chain Monte Carlo and Exact Conditional Tests with Three-Way Contingency Tables,” Master’s thesis, Naval Postgraduate School.
   Google Scholar
• Ogawa, M., Hara, H., and Takemura, A. (2013), “Graver Basis for an Undirected Graph and its Application to Testing the Beta Model of Random Graphs,” Annals of Institute of Statistical Mathematics, 65, 191–212. DOI: 10.1007/s10463-012-0367-8.
   Web of Science ®Google Scholar
• Onn, S., Thoma, A., and Vladoiu, M. (2022), “Asymptotic Behavior of Markov Complexity of Matrices.” https://arxiv.org/abs/2210.01686
   Google Scholar
• Petrović, S., and Stokes, E. (2013), “Betti Numbers of Stanley-Reisner Rings Determine Hierarchical Markov Degrees,” Journal of Algebraic Combinatorics, 37, 667–682. DOI: 10.1007/s10801-012-0381-1.
   Web of Science ®Google Scholar
• Petrović, S., Rinaldo, A., and Fienberg, S. E. (2010), “Algebraic Statistics for a Directed Random Graph Model with Reciprocation,” in Algebraic Methods in Statistics and Probability II, volume 516 of Contemporary Mathematics, eds. M. Viana and H. Wynn, pp. 261–283, Providence RI: American Mathematical Society.
   Google Scholar
• Rapallo, F., and Yoshida, R. (2010), “Markov Bases and Subbases for Bounded Contingency Tables,” Annals of the Institute of Statistical Mathematics, 62, 85–805. DOI: 10.1007/s10463-010-0289-2.
   Web of Science ®Google Scholar
• Rasch, G. (1960), Probabilistic Models for Some Intelligence and Attainment Tests, Chicago, IL: University of Chicago Press.
   Google Scholar
• Rauh, J., and Sullivant, S. (2016), “Lifting Markov Bases and Higher Codimension Toric Fiber Products,” Journal of Symbolic Computation, 74, 276–307. DOI: 10.1016/j.jsc.2015.07.003.
   Web of Science ®Google Scholar
• Rinaldo, A., Petrović, S., and Fienberg, S. E. (2013), “Maximum Likelihood Estimation in the Beta Model,” Annals of Statistics, 41, 1085–1110.
   Web of Science ®Google Scholar
• Schrijver, A. (1999), Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, Chichester: Wiley.
   Google Scholar
• Stanley, C., and Windisch, T. (2018), “Heat-Bath Random Walks with Markov Bases,” Advances in Applied Mathematics, 92, 122–143. DOI: 10.1016/j.aam.2017.08.002.
   Web of Science ®Google Scholar
• Sturmfels, B. (1996), Gröbner bases and Convex Polytopes. University Lecture Series, no. 8. Providence, RI: American Mathematical Society.
   Google Scholar
• Sullivant, S. (2021), Algebraic Statistics. Graduate Studies in Mathematics, Providence, RI: American Mathematical Society.
   Google Scholar
• Takken, A. (2000), Monte Carlo Goodness-of-Fit Tests for Discrete Data,” PhD thesis, Dept. Statistics, Stanford University.
   Google Scholar
• Tatakis, C., and Thoma, A. (2022), “On the Relative Size of Toric Bases,” Journal of Algebra and Its Applications, 21, 2250079. DOI: 10.1142/S0219498822500797.
   Web of Science ®Google Scholar
• Windisch, T. (2015), “Rapid Mixing and Markov Bases,” SIAM Journal of Discrete Mathematics, 30, 2130–2145. Available at arXiv:1505.03018. DOI: 10.1137/15M1022045.
   Web of Science ®Google Scholar
• Yoshida, R. (2010), “Open Problems on Connectivity of Fibers with Positive Margins in Multi-Dimensional Contingency Tables,” The Journal of Algebraic Statistics, 1, 13–26, 2010. DOI: 10.18409/jas.v1i1.5.
   Google Scholar
• Yoshida, R., and Barnhill, D. (2023), “Connecting Tables with Allowing Negative Cell Counts,” Available at arXiv:2205.07167.
   Google Scholar
• Zhangm J., and Chen, Y. (2013), “Sampling for Conditional Inference on Network Data,” Journal of the American Statistical Association, 108, 1295–1307. DOI: 10.1080/01621459.2012.758587.
   Web of Science ®Google Scholar