Premium
Random generation of 2× n contingency tables
Author(s) -
Hernek Diane
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199808)13:1<71::aid-rsa4>3.0.co;2-p
Subject(s) - combinatorics , mathematics , contingency table , integer (computer science) , markov chain , discrete mathematics , monte carlo method , set (abstract data type) , distribution (mathematics) , column (typography) , statistics , computer science , mathematical analysis , programming language , geometry , connection (principal bundle)
Let r =( r 1 , r 2 ) and c =( c 1 ,…, c n ) be positive integer partitions of N . Let Σ rc denote the set of all 2× n arrays of nonnegative integers whose i th row sums to r i and j th column sums to c j . We consider the problem of randomly generating an element from the uniform distribution over Σ rc . This problem arises in statistics where random samples are used to decide whether two attributes are independent. In this paper, we present a Markov chain Monte Carlo algorithm for this problem and give the first general polynomial bounds on its running time. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 71–79, 1998