Sampling Contingency Tables Using Markov Moves Based on Linear Programming
Lawrence H. Cox
National Institute of Statistical Sciences, Ellicott City, United States

Numerous problems in mathematics and statistics are concerned with frequency tables and other arrangements of integer values, represented as feasible solutions to the system Ax = b: A, b, x integer and x0. An important statistical application is an iterative MCMC algorithm due to Diaconis-Sturmfels for sampling from discrete distributions subject to certain marginal totals (A) held fixed (b): beginning at a current solution s, an integer move m (integer solution of An = 0, unrestricted in sign) is selected subject to appropriate conditions on the Markov chain; then, based on a Metropolis step, either the new solution s + n or the current solution s enters the sample. This method encounters difficulties when the set of candidate moves is large or not fully known, which is often the case. In earlier work, I showed that for the class of frequency tables known as tables of network type the selection step could be replaced by a computationally efficient construction step based on mathematical networks. Current work extends the construction step to Markov moves in any integer linear program–hence any set of contingency tables subject to fixed marginals–based on general linear programming. The latter is a theoretical advance whose computational performance remains untested.

Keywords: MCMC; Linear programming; Tables of network type; Sampling

Biography: Dr. Lawrence H. Cox is Assistant Director for Official Statistics, National Institute of Statistical Sciences, USA. He is an elected member of ISI and Fellow of the American Statistical Association. Prior positions include Associate Director for Research and Methodology, US National Center for Health Statistics, Senior Mathematical Statistician, for both US Census Bureau and US EPA, and Director, Board on Mathematical Sciences, US National Academy of Sciences.