×

Distance-reducing Markov bases for sampling from a discrete sample space. (English) Zbl 1085.62076

From the introduction: A Markov basis for sampling from a discrete conditional distribution is usually studied in the framework of a toric ideal and its Gröbner basis. For the case of a \(3\times 3\times K\) contingency table with fixed two-dimensional marginals, in [Aust. N. Z. J. Stat. 45, No. 2, 229–249 (2003; Zbl 1064.62068)] we used a more elementary approach to derive a unique minimal Markov basis. The approach was based on exhaustive consideration of sign patterns when the \(L_1\)-norm (1-norm) between two contingency tables with the same margmals is minimized. In order to prove that a candidate set \(\mathcal B\) of moves is a Markov basis, we have shown that the 1-norm between two contingency tables can always be decreased by an element of \(\mathcal B\).
In order to study a minimal Markov basis and its uniqueness for other models, in [Ann. Inst. Stat. Math. 56, No. 1, 1–17 (2004; Zbl 1049.62068)] we considered whether two elements of the same fibre (reference set) are mutually accessible by a set of lower-degree moves and derived some results on the characterization of minimal Markov bases. Note that the notion of mutual accessibility is not directly related to any metric on the fibres. Therefore although the approaches in these two papers were similar, they were different in explicit consideration of the metric on the fibres.
In this paper we explicitly consider the 1-norm on the fibres in the general framework of our paper from 2004 and derive some characterizations of 1-norm-reducing Markov bases.

MSC:

62H17 Contingency tables
62D05 Sampling theory, sample surveys
05C90 Applications of graph theory
62B05 Sufficient statistics and fields

Software:

4ti2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aoki, S. and Takemura, A. (2003a) Minimal basis for connected Markov chain over 3 3 3 3 K contingency tables with fixed two-dimensional marginals. Aust. N. Z. J. Statist., 45, 229-249. · Zbl 1064.62068 · doi:10.1111/1467-842X.00278
[2] Aoki, S. and Takemura, A. (2003b) Invariant minimal Markov basis for sampling contingency tables with fixed marginals. Technical Report METR 03-25, Department of Mathematical Engineering and Information Physics, University of Tokyo. Submitted for publication. · Zbl 1064.62068
[3] Aoki, S. and Takemura, A. (2005) Markov chain Monte Carlo exact tests for incomplete two-way contingency tables. J. Statist. Comput. Simulation. · Zbl 1076.62060 · doi:10.1080/00949650410001690079
[4] Bubley, R. and Dyer, M. (1997) Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 223-231. Los Alamitos, CA: IEEE Computer Society Press.
[5] Diaconis, P. and Saloff-Coste, L. (1998) What do we know about the Metropolis algorithm?. J. Comput. System Sci., 57, 20-36. · Zbl 0920.68054 · doi:10.1006/jcss.1998.1576
[6] Diaconis, P. and Sturmfels, B. (1998) Algebraic algorithms for sampling from conditional distributions. Ann. Statist., 26, 363-397. · Zbl 0952.62088 · doi:10.1214/aos/1030563990
[7] Diaconis, P., Eisenbud, D. and Sturmfels, B. (1998) Lattice walks and primary decomposition. In B.E. Sagan and R.P. Stanley (eds), Mathematical Essays in Honor of Gian-Carlo Rota, pp. 173-193. Boston: Birkhäuser. · Zbl 0962.05010
[8] Dinwoodie, I. H. (1998) The Diaconis-Sturmfels algorithm and rules of succession. Bernoulli, 4, 401-410. · Zbl 0914.60038 · doi:10.2307/3318722
[9] Dobra, A. (2003) Markov bases for decomposable graphical models. Bernoulli, 9, 1093-1108. · Zbl 1053.62072 · doi:10.3150/bj/1072215202
[10] Guo, S.W. and Thompson, E.A. (1992) Performing the exact test of Hardy-Weinberg proportion for multiple alleles. Biometrika, 48, 361-372. · Zbl 0825.62835 · doi:10.2307/2532296
[11] Hemmecke, R. and Hemmecke, R. (2003) 4ti2 Version 1-1 Computation of Hilbert bases, Graver bases, toric Gröbner bases, and more. Available at http://www.4ti2.de. URL: · Zbl 1019.68144
[12] Hibi, T. (2003) Gröbner Bases. Tokyo: Asakura Shoten (in Japanese). · Zbl 1034.90009
[13] Ohsugi, H. and Hibi, T. (2003) Indispensable binomials of toric ideals. Submitted for publication. · Zbl 1093.13020
[14] Sturmfels, B. (1995) Gröbner Bases and Convex Polytopes. Providence, RI: American Mathematical Society. · Zbl 0856.13020
[15] Takemura, A. and Aoki, S. (2004) Some characterizations of minimal Markov basis for sampling from discrete conditional distributions. Ann. Inst. Statist. Math., 56, 1-17. · Zbl 1049.62068 · doi:10.1007/BF02530522
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.