zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Algebraic algorithms for sampling from conditional distributions. (English) Zbl 0952.62088
This paper aims to describe the construction of new Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic. Section 2 introduces the necessary stochastic and statistical background. Section 3 contains the main contribution of the paper: it shows how to compute a Markov basis using tools from computational algebra. More precisely, to find a Markov basis is proved to be equivalent to finding a set of generators of an ideal in a polynomial ring, using Gröbner bases. To represent this ideal in a way suitable for computation is illustrated by MATHEMATICA and MAPLE programs. The next sections of the paper include detailed treatments of the proposed technique for some important special cases: contingency tables (Section 4), logistic regression (in Section 5), and the spectral analysis of permutation data (Section 6).

MSC:
62M99Inference from stochastic processes
65C60Computational problems in statistics
13P10Gröbner bases; other bases for ideals and modules
62F25Parametric tolerance and confidence regions
62H17Contingency tables (statistics)
Software:
Maple; Mathematica
WorldCat.org
Full Text: DOI
References:
[1] AGRESTI, A. 1990. Categorical Data Analy sis. Wiley, New York. Z.
[2] AGRESTI, A. 1992. A survey of exact inference for contingency tables. Statist. Sci. 7 131 177. Z. · Zbl 0955.62587 · doi:10.1214/ss/1177011454
[3] ALDOUS, D. 1987. On the Markov chain stimulation method for uniform combinatorial distributions and simulated annealing. Probab. Engrg. Infom. Sci. 1 33 46. Z. · Zbl 1133.60327 · doi:10.1017/S0269964800000267
[4] ANDREWS, D. and HERZBERG, A. 1985. Data. Springer, New York. Z.
[5] BAGLIVIO, J., OLIVIER, D. and PAGANO, M. 1988. Methods for the analysis of contingency tables with large and small cell counts. J. Amer. Statist. Assoc. 83 1006 1013. Z. JSTOR: · doi:10.2307/2290127 · http://links.jstor.org/sici?sici=0162-1459%28198812%2983%3A404%3C1006%3AMFTAOC%3E2.0.CO%3B2-9&origin=euclid
[6] BAGLIVIO, J., OLIVIER, D. and PAGANO, M. 1992. Methods for exact goodness-of-fit tests. J. Amer. Statist. Assoc. 87 464 469.Z. JSTOR: · Zbl 0850.62392 · doi:10.2307/2290278 · http://links.jstor.org/sici?sici=0162-1459%28199206%2987%3A418%3C464%3AMFEGT%3E2.0.CO%3B2-Y&origin=euclid
[7] BAGLIVIO, J., OLIVIER, D. and PAGANO, M. 1993. Analy sis of discrete data: rerandomization methods and complexity. Technical report, Dept. Mathematics, Boston College. Z.
[8] BAy ER, D. and STILLMAN, M. 1989. MACAULAY: a computer algebra sy stem for algebraic geometry. Available via anony mous ftp from zariski.harvard.edu. Z.
[9] BELISLE, C., ROMEIJN, H. and SMITH, R. 1993. Hit and run algorithms for generating multivariate distributions. Math. Oper. Res. 18 255 266. Z. JSTOR: · Zbl 0771.60052 · doi:10.1287/moor.18.2.255 · http://links.jstor.org/sici?sici=0364-765X%28199305%2918%3A2%3C255%3AHAFGMD%3E2.0.CO%3B2-U&origin=euclid
[10] BESAG, J. and CLIFFORD, P. 1989. Generalized Monte Carlo significance tests. Biometrika 76 633 642. Z. JSTOR: · Zbl 0679.62033 · doi:10.1093/biomet/76.4.633 · http://links.jstor.org/sici?sici=0006-3444%28198912%2976%3A4%3C633%3AGMCST%3E2.0.CO%3B2-K&origin=euclid
[11] BIRCH, B. W. 1963. Maximum likelihood in three-way contingency tables. J. Roy. Statist. Soc. Ser. B 25 220 233. Z. JSTOR: · Zbl 0121.14001 · http://links.jstor.org/sici?sici=0035-9246%281963%2925%3A1%3C220%3AMLITCT%3E2.0.CO%3B2-J&origin=euclid
[12] BISHOP, Y., FINEBERG, S. and HOLLAND, P. 1975. Discrete Multivariate Analy sis. MIT Press. Z.
[13] BJORNER, A., LAS VERGNAS, M., STURMFELS, B., WHITE, N. and ZIEGLER, G. 1993. Oriented \" Matroids. Cambridge Univ. Press. Z.
[14] BOKOWSKI, J. and RICHTER-GEBERT, J. 1990. On the finding of final poly nomials. European J. Combin. 11 21 34. Z. · Zbl 0693.05021 · doi:10.1016/S0195-6698(13)80052-2
[15] BOKOWSKI, J. and RICHTER-GEBERT, J. 1991. On the classification of non-realizable oriented matroids. II. Preprint, T. H. Darmstadt. Z.
[16] BOKENHOLT, U. 1993. Applications of Thurstonian models to ranking data. Probability Models änd Statistical Analy sis for Ranking Data. Lecture Notes in Statist. 80 157 172. Springer, New York. Z. · Zbl 0764.62097
[17] BROWN, L. D. 1990. An ancillarity paradox which appears in multiple linear regression. Ann. Statist. 18 471 538. Z. · Zbl 0721.62011 · doi:10.1214/aos/1176347602
[18] CHRISTENSEN, R. 1990. Log-Linear Models. Springer, New York. Z. · Zbl 0711.62050
[19] CHUNG, F., GRAHAM, R. and YAU, S. T. 1996. On sampling with Markov chains. Random Structures Algorithms 9 55 77. Z. · Zbl 0861.60079 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<55::AID-RSA4>3.0.CO;2-A
[20] COHEN, A., KEMPERMAN, J. and SACKROWITZ, H. 1994. Unbiased testing in exponential family regression. Ann. Statist. 22 1931 1946. Z. · Zbl 0824.62011 · doi:10.1214/aos/1176325765
[21] CONTI, P. and TRAVERSO, C. 1991. Buchberger algorithm and integer programming. Proceedings AAECC-9. Lecture Notes in Comp. Sci. 539 130 139. Springer, New York. Z. · Zbl 0771.13014
[22] COX, D. 1958. Some problems connected with statistical inference. Ann. Math. Statist. 29 357 372. Z. · Zbl 0088.11702 · doi:10.1214/aoms/1177706618
[23] COX, D. 1988. Some aspects of conditional and asy mptotic inference. Sankhy a Ser. A 50 314 337.
[24] COX, D., LITTLE, J. and O’SHEA, D. 1992. Ideals, Varieties, and Algorithms. Springer, New York. Z.
[25] CROON, M. 1989. Latent class models for the analysis of rankings. In New Developments in Z. Psy chological Choice Modeling G. De Solte, H. Feger and K. C. Klauer, eds. 99 121. North-Holland, Amsterdam. Z.
[26] DARROCH, J., LAURITZEN, S. and SPEED T. 1980. Markov fields a log-linear interaction models for contingency tables. Ann. Statist. 8 522 539. Z. · Zbl 0444.62064 · doi:10.1214/aos/1176345006
[27] DIACONIS, P. 1988. Group Representations in Probability and Statistics. IMS, Hay ward, CA. Z. · Zbl 0695.60012
[28] DIACONIS, P. 1989. A generalization of spectral analysis with application to ranked data. Ann. Statist. 17 949 979. Z. · Zbl 0688.62005 · doi:10.1214/aos/1176347251
[29] DIACONIS, P. and EFRON, B. 1985. Testing for independence in a two-way table: new interpretations for the chi-square statistic. Ann. Statist. 13 845 905. Z. · Zbl 0593.62040 · doi:10.1214/aos/1176349634
[30] DIACONIS, P. and EFRON, B. 1987. Probabilistic-geometric theorems arising from the analysis of contingency tables. In Contributions to the Theory and Application of Statistics: A Z. Volume in Honor of Herbert Solomon A. Gelfand, ed.. Academic Press, New York. Z. · Zbl 0709.60566
[31] DIACONIS, P., EISENBUD, D. and HOLMES, S. 1997. Speeding up algebraic random walks. Dept. Mathematics, Brandeis Univ. Preprint. Z.
[32] DIACONIS, P., EISENBUD, D. and STURMFELS, B. 1996. Lattice walks and primary decompositions. Z. In Proceedings of the Rota Fest B. Sagan, ed.. To appear. Z. · Zbl 0962.05010
[33] DIACONIS, P. and FREEDMAN, D. 1987. A dozen deFinetti-sty le results in search of a theory. Ann. Inst. H. Poincare 23 397 423. Ź. · Zbl 0619.60039
[34] DIACONIS, P. and GANGOLLI, A. 1995. Rectangular array s with fixed margins. In Discrete Z. Probability and Algorithms D. Aldous, et al., eds.. 15 41. Springer, New York. Z. · Zbl 0839.05005
[35] DIACONIS, P., GRAHAM, R. and STURMFELS, B. 1996. Primitive partition identities. Combinatorics. Paul Erdos Is Eighty 2 173 192. Z. · Zbl 0852.05014
[36] DIACONIS, P., HOLMES, S. and NEALE, R. 1997. A nonreversible Markov chain sampling method. Technical report, Biometry, Cornell Univ. Z.
[37] DIACONIS, P. and RABINOWITZ, A. 1997. Conditional inference for logistic regression. Technical report, Stanford Univ. Z.
[38] DIACONIS, P. and SALOFF-COSTE, L. 1995a. Random walk on contingency tables with fixed row and column sums. Dept. Mathematics, Harvard Univ., Preprint. Z. · Zbl 1006.60095 · doi:10.1023/A:1015170205728
[39] DIACONIS, P. and SALOFF-COSTE, L. 1995b. What do we know about the Metropolis algorithm. Technical report, Dept. Mathematics, Harvard Univ. Z. · Zbl 1006.60095 · doi:10.1023/A:1015170205728
[40] DIACONIS, P. and SALOFF-COSTE, L. 1996a. Nash inequalities for finite Markov chains. J. Theoret. Probab. 9 459 510. Z. · Zbl 1006.60095 · doi:10.1023/A:1015170205728
[41] DIACONIS, P. and SALOFF-COSTE, L. 1996b. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695 750. Z. · Zbl 1006.60095 · doi:10.1023/A:1015170205728
[42] DIACONIS, P. and STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36 61. Z. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[43] Dy ER, R., KANNAN, R. and MOUNT, J. 1995. Sampling contingency tables. Random Structures Algorithms. To appear. Z.
[44] EFRON, B. and HINKLEY, D. 1978. Assessing the accuracy of the MLE: observed versus expected Z. Fisher information with discussion. Biometrika 65 457 487. Z. JSTOR: · Zbl 0401.62002 · doi:10.1093/biomet/65.3.457 · http://links.jstor.org/sici?sici=0006-3444%28197812%2965%3A3%3C457%3AATAOTM%3E2.0.CO%3B2-Y&origin=euclid
[45] FARRELL, R. 1971. The necessity that a conditional procedure be almost every where admissible. Z. Wahrsch. Verw. Gebiete 19 57 66. Z. Z. · Zbl 0203.51403 · doi:10.1007/BF01111209
[46] FISHER, R. 1925. Statistical Methods for Research Workers, 1st ed. 14th ed. 1970. Oliver and Boy d, Edinburgh. Z. · Zbl 51.0414.08
[47] FISHER, R. 1950. The significance of deviations from expectation in a Poisson series. Biometrics 6 17 24. Z.
[48] FISHER, R., THORNTON, H. and MACKENZIE, N. 1922. The accuracy of the plating method of estimating the density of bacterial populations. Ann. Appl. Biology 9 325 359. Z.
[49] FULTON, W. 1993. Introduction to Toric Varieties. Princeton Univ. Press. Z. · Zbl 0813.14039
[50] GANGOLLI, A. 1991. Convergence bounds for Markov chains and applications to sampling. Ph.D. thesis, Dept. Computer Science, Stanford Univ.
[51] GLONEK, G. 1987. Some aspects of log linear models. Ph.D. thesis, School of Math. Sciences, Flinders Univ. South Australia. Z.
[52] GOODMAN, L. 1970. The multivariate analysis of qualitative data: interactions among multiple classifications. J. Amer. Statist. Assoc. 65 226 256. Z.
[53] GUO, S. and THOMPSON, E. 1992. Performing the exact test for Hardy Weinberg proportion for multiple alleles. Biometrics 48 361 372. Z. · Zbl 0825.62835 · doi:10.2307/2532296
[54] HABERMAN, S. 1978. Analy sis of Qualitative Data 1, 2. Academic Press, Orlando, FL. Z.
[55] HAMMERSLY, J. and HANDSCOMB, D. 1964. Monte Carlo Methods. Wiley, New York. Z.
[56] HARRIS, J. 1992. Algebraic Geometry: A First Course. Springer, New York. Z. · Zbl 0779.14001
[57] HERNEK, D. 1997. Random generation and counting of rectangular array s with fixed margins. Dept. Mathematics, Preprint, UCLA. Z.
[58] HOLMES, R. and JONES, L. 1996. On uniform generation of two-way tables with fixed margins and the conditional volume test of Diaconis and Efron. Ann. Statist. 24 64 68. Z. · Zbl 0888.62060 · doi:10.1214/aos/1033066199
[59] HOLMES, S. 1995. Examples for Stein’s method. Preprint, Dept. Statistics, Stanford Univ. Z.
[60] JENSEN, J. 1991. Uniform saddlepoint approximations and log-convex densities. J. Roy. Statist. Soc. Ser. B 157 172. Z. Z. JSTOR: · Zbl 0800.62081 · http://links.jstor.org/sici?sici=0035-9246%281991%2953%3A1%3C157%3AUSAALD%3E2.0.CO%3B2-1&origin=euclid
[61] KIEFER, J. 1977. Conditional confidence statements and confidence estimators with discussion. J. Amer. Statist. Assoc. 72 789 827. Z. JSTOR: · Zbl 0375.62023 · doi:10.2307/2286460 · http://links.jstor.org/sici?sici=0162-1459%28197712%2972%3A360%3C789%3ACCSACE%3E2.0.CO%3B2-9&origin=euclid
[62] KOLASSA, J. and TANNER, M. 1994. Approximate conditional inference in exponential families via the Gibbs sample. J. Amer. Statist. Assoc. 89 697 702. Z. JSTOR: · Zbl 0803.62013 · doi:10.2307/2290874 · http://links.jstor.org/sici?sici=0162-1459%28199406%2989%3A426%3C697%3AACIIEF%3E2.0.CO%3B2-K&origin=euclid
[63] KOLASSA, J. and TANNER, M. 1996. Approximate Monte Carlo conditional inference. Dept. Statistics, Northwestern Univ. Preprint. Z.
[64] KONG, F. 1993. Edgeworth expansions for conditional distributions in logistic regression models. Technical report, Dept. Statistics, Columbia Univ. Z.
[65] KONG, F. and LEVIN, B. 1993. Edgeworth expansions for the sum of discrete random vectors and their applications in generalized linear models. Technical report, Dept. Statistics, Columbia Univ. Z.
[66] LANGE, K. and LAZZERONI, L. 1997. Markov chains for Monte Carlo tests of genetic equilibrium in multidimensional contingency tables. Ann. Statist. To appear. Z. · Zbl 0871.62094 · doi:10.1214/aos/1034276624
[67] LARNTZ, K. 1978. Small-sample comparison of exact levels for chi-squared goodness-of-fit statistics. J. Amer. Statist. Assoc. 73 253 263. Z. · Zbl 0414.62022 · doi:10.2307/2286650
[68] LAURITZEN, S. 1996. Graphical Models. Oxford Univ. Press. Z.
[69] LEHMANN, E. 1986. Testing Statistical Hy potheses, 2nd ed. Wiley, New York. Z.
[70] LEVIN, B. 1992. On calculations involving the maximum cell frequency. Comm. Statist. Z.
[71] LEVIN, B. 1992. Tests of odds ratio homogeneity with improved power in sparse fourfold tables. Comm. Statist. Theory Methods 21 1469 1500. Z. · Zbl 0775.62007 · doi:10.1080/03610929208830860
[72] MARDEN, J. 1995. Analy zing and Modeling Rank Data. Chapman and Hall, London. Z. · Zbl 0853.62006
[73] MAy R, E. and MEy ER, A. 1982. The complexity of the word problem for commutative semigroups and poly nomial ideals. Adv. in Math. 46 305 329. Z. · Zbl 0506.03007 · doi:10.1016/0001-8708(82)90048-2
[74] MCCULLOGH, P. 1985. On the asy mptotic distribution of Pearson’s statistic in linear exponential family models. International Statistical Review 53 61 67. Z. JSTOR: · Zbl 0575.62020 · doi:10.2307/1402880 · http://links.jstor.org/sici?sici=0306-7734%28198504%2953%3A1%3C61%3AOTADOP%3E2.0.CO%3B2-5&origin=euclid
[75] MCCULLOUGH, P. 1986. The conditional distribution of goodness-to-fit statistics for discrete data. J. Amer. Statist. Assoc. 81 104 107. Z.
[76] MEHTA, C. and PATEL, N. 1983. A network algorithm for performing Fisher’s exact test in r c contingency tables. J. Amer. Statist. Assoc. 78 427 434. Z. JSTOR: · Zbl 0545.62039 · doi:10.2307/2288652 · http://links.jstor.org/sici?sici=0162-1459%28198306%2978%3A382%3C427%3AANAFPF%3E2.0.CO%3B2-B&origin=euclid
[77] NEy MAN, J. 1937. Outline of a theory of statistical estimation based on the classical theory of probability. Philos. Trans. 236 333 380. Z. · Zbl 0017.12403 · doi:10.1098/rsta.1937.0005
[78] ODOROFF, C. 1970. A comparison of minimum logit chi-square estimation and maximum likelihood estimation in 2 2 2 and 3 2 2 contingency tables: tests for interaction. J. Amer. Statist. Assoc. 65 1617 1631. Z. · Zbl 0224.62028
[79] PROPP, J. and WILSON, D. 1986. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9 232 252. Z. · Zbl 0859.60067 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O
[80] REID, N. 1995. The roles of conditioning in inference. Statist. Sci. 10 138 199. Z. Z. · Zbl 0955.62524 · doi:10.1214/ss/1177010027
[81] SAVAGE, L. 1976. On rereading R. A. Fisher with discussion. Ann. Statist. 4 441 450. Z. · Zbl 0325.62008 · doi:10.1214/aos/1176343456
[82] SCHRIJVER, A. 1986. Theory of Linear and Integer Programming. Wiley, New York. · Zbl 0665.90063
[83] SINCLAIR, A. 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston. \" Z. · Zbl 0780.68096
[84] SKOVGAARD, I. 1987. Saddlepoint expansions for conditional distributions. J. Appl. Probab. 24 875 887. Z. SNEE 1974. Graphical display of two-way contingency tables. Amer. Statist. 38 9 12. Z. JSTOR: · Zbl 0638.62018 · doi:10.2307/3214212 · http://links.jstor.org/sici?sici=0021-9002%28198712%2924%3A4%3C875%3ASEFCD%3E2.0.CO%3B2-M&origin=euclid
[85] STANLEY, R. 1980. Decompositoin of rational convex poly topes. Ann. Discrete Math. 6 333 342. Z. · doi:10.1016/S0167-5060(08)70717-9
[86] STEIN, C. 1986. Approximate Computation of Expectations. IMS, Hay ward, CA. Z. · Zbl 0721.60016
[87] STURMFELS, B. 1991. Grobner bases of toric varieties. Tohoko Math. J. 43 249 261. \" Z. · Zbl 0714.14034 · doi:10.2748/tmj/1178227496
[88] STURMFELS, B. 1992. Asy mptotic analysis of toric ideals. Mem. Fac. Sci. Ky ushu Univ. Ser. A 46 217 228. Z. · Zbl 0784.14024 · doi:10.2206/kyushumfs.46.217
[89] STURMFELS, B. 1996. Grobner Bases and Convex Poly topes. Amer. Math. Soc., Providence, RI. \" Z.
[90] THOMAS, R. 1995. A geometric Buchberger algorithm for integer programming. Math. Oper. Res. 20 864 884. Z. JSTOR: · Zbl 0846.90079 · doi:10.1287/moor.20.4.864 · http://links.jstor.org/sici?sici=0364-765X%28199511%2920%3A4%3C864%3AAGBAFI%3E2.0.CO%3B2-X&origin=euclid
[91] VIRAG, B. 1997. Random walks on finite convex sets of lattice points. Technical report, Dept. Statistics, Univ. California, Berkeley. Z. · Zbl 0918.60054 · doi:10.1023/A:1022612814891
[92] WEISPFENNING, V. 1987. Admissible orders and linear forms. ACM SIGSAM Bulletin 21 16 18. Z. 2 · Zbl 0655.13017 · doi:10.1145/24554.24557
[93] YARNOLD, J. 1970. The minimum expectation in X goodness-of-fit tests and the accuracy of approximations for the null distribution. J. Amer. Statist. Assoc. 65 864 886. Z. JSTOR: · doi:10.2307/2284594 · http://links.jstor.org/sici?sici=0162-1459%28197006%2965%3A330%3C864%3ATMEIGO%3E2.0.CO%3B2-L&origin=euclid
[94] YATES, F. 1984. Tests of significance for 2 2 contingency tables. J. Roy. Statist. Soc. Ser. A 147 426 463. JSTOR: · Zbl 0573.62050 · doi:10.2307/2981577 · http://links.jstor.org/sici?sici=0035-9238%281984%29147%3A3%3C426%3ATOSFCT%3E2.0.CO%3B2-U&origin=euclid
[95] CORNELL UNIVERSITY BERKELEY, CALIFORNIA 94720
[96] ITHACA, NEW YORK 14853 E-MAIL: ims@math.cornell.edu