Running Markov chain without Markov basis

DOI10.1007/978-1-4614-3719-2zbMATH Open1304.62015arXiv1109.0078OpenAlexW2496300389MaRDI QIDQ409079FDOQ409079

Satoshi Aoki, Hisayuki Hara, Akimichi Takemura

Publication date: 12 April 2012

Published in: Springer Series in Statistics, Harmony of Gröbner Bases and the Modern Industrial Society - The Second CREST-CSBM International Conference (Search for Journal in Brave)

Abstract: The methodology of Markov basis initiated by Diaconis and Sturmfels(1998) stimulated active research on Markov bases for more than ten years. It also motivated improvements of algorithms for Grobner basis computation for toric ideals, such as those implemented in 4ti2. However at present explicit forms of Markov bases are known only for some relatively simple models, such as the decomposable models of contingency tables. Furthermore general algorithms for Markov bases computation often fail to produce Markov bases even for moderate-sized models in a practical amount of time. Hence so far we could not perform exact tests based on Markov basis methodology for many important practical problems. In this article we propose to use lattice bases for performing exact tests, in the case where Markov bases are not known. Computation of lattice bases is much easier than that of Markov bases. With many examples we show that the approach with lattice bases is practical. We also check that its performance is comparable to Markov bases for the problems where Markov bases are known.

Full work available at URL: https://arxiv.org/abs/1109.0078

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational methods in Markov chains (60J22) Parametric hypothesis testing (62F03) Inference from stochastic processes (62M99) Contingency tables (62H17) Research exposition (monographs, survey articles) pertaining to statistics (62-02) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Cited In (46)

• Markov chain Monte Carlo methods for the regular two-level fractional factorial designs and cut ideals
• Statistical testing procedure for the interaction effects of several controllable factors in two-valued input-output systems
• Exact Goodness‐of‐Fit Testing for the Ising Model
• Markov degree of the Birkhoff model
• Introduction to Computational Algebraic Statistics
• Conditional inference of Poisson models and information geometry: an ancillary review
• Analysis of the weighted kappa and its maximum with Markov moves
• Conditional inference given partial information in contingency tables using Markov bases
• Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates
• Markov Bases: A 25 Year Update
• When lattice bases are Markov bases
• Some rapidly mixing hit-and-run samplers for latent counts in linear inverse problems
• Markov complexity of monomial curves
• On atomic density of numerical semigroup algebras
• Markov chain Monte Carlo test of toric homogeneous Markov chains
• Toric ideals of characteristic imsets via quasi-independence gluing
• Quasi-independence models with rational maximum likelihood estimator
• Minimal Markov Basis for Tests of Main Effect Models for 2^p-1Fractional Factorial Designs of Resolutionp
• Equivariant lattice bases
• Title not available (Why is that?)
• Connecting tables by allowing negative cell counts
• The fiber dimension of a graph
• Symmetrically Colored Gaussian Graphical Models with Toric Vanishing Ideals
• Blow-up algebras, determinantal ideals, and Dedekind-Mertens-like formulas
• Toric algebra of hypergraphs
• Markov bases and structural zeros
• Goodness of fit for log-linear network models: dynamic Markov bases using hypergraphs
• Title not available (Why is that?)
• Bouquet algebra of toric ideals
• Nonlinear algebra and applications
• Editorial: A new beginning
• The norm of the saturation of a binomial ideal, with applications to Markov bases
• Exact test of goodness of fit for binomial distribution
• Finite space Kantorovich problem with an MCMC of table moves
• Markov Bases and Designed Experiments
• A survey of discrete methods in (algebraic) statistics for networks
• Hybrid schemes for exact conditional inference in discrete exponential families
• Retracts and algebraic properties of cut algebras
• Markov-chain Monte Carlo methods for the Box-Behnken designs and centrally symmetric configurations
• A novel association test for rare variants based on algebraic statistics
• The Markov complexity of book graphs
• Information Geometry of the Probability Simplex: A Short Course
• Exact tests for singular network data
• Orbit-based conditional tests. A link between permutations and Markov bases
• Connecting the latent multinomial
• Counting subsets of contingency tables

Uses Software

• 4ti2

Recommendations

• Markov Chains 👍 👎
• Monte Carlo without chains 👍 👎
• Markov chains and de-initializing processes 👍 👎
• Approximating Markov chains. 👍 👎
• Markov Chains 👍 👎
• Skip-free Markov chains 👍 👎
• Runs in Markov sequences 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Running Markov chain without Markov basis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409079)