How to generate uniform samples on discrete sets using the splitting method

Glynn, Peter W., Dolgin, Andrey, Rubinstein, Reuven Y. and Vaisman, Radislav (2010) How to generate uniform samples on discrete sets using the splitting method. Probability in the Engineering and Informational Sciences, 24 3: 405-422. doi:10.1017/S0269964810000057

Author Glynn, Peter W.
Dolgin, Andrey
Rubinstein, Reuven Y.
Vaisman, Radislav
Title How to generate uniform samples on discrete sets using the splitting method
Journal name Probability in the Engineering and Informational Sciences   Check publisher's open access policy
ISSN 0269-9648
Publication date 2010
Sub-type Article (original research)
DOI 10.1017/S0269964810000057
Volume 24
Issue 3
Start page 405
End page 422
Total pages 18
Place of publication Cambridge, United Kingdom
Publisher Cambridge University Press
Language eng
Subject 1803 Management Science and Operations Research
1804 Statistics, Probability and Uncertainty
2209 Industrial and Manufacturing Engineering
2613 Statistics and Probability
Abstract The goal of this work is twofold. We show the following: 1. In spite of the common consensus on the classic Markov chain Monte Carlo (MCMC) as a universal tool for generating samples on complex sets, it fails to generate points uniformly distributed on discrete ones, such as that defined by the constraints of integer programming. In fact, we will demonstrate empirically that not only does it fail to generate uniform points on the desired set, but typically it misses some of the points of the set.2. The splitting, also called the cloning method - originally designed for combinatorial optimization and for counting on discrete sets and presenting a combination of MCMC, like the Gibbs sampler, with a specially designed splitting mechanismcan also be efficiently used for generating uniform samples on these sets. Without introducing the appropriate splitting mechanism, MCMC fails. Although we do not have a formal proof, we guess (conjecture) that the main reason that the classic MCMC is not working is that its resulting chain is not irreducible. We provide valid statistical tests supporting the uniformity of generated samples by the splitting method and present supportive numerical results.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Fri, 07 Feb 2014, 10:10:29 EST by Radislav Vaisman on behalf of Scholarly Communication and Digitisation Service