# 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, AndreyRubinstein, Reuven Y.Vaisman, Radislav How to generate uniform samples on discrete sets using the splitting method Probability in the Engineering and Informational Sciences   Check publisher's open access policy 0269-96481469-8951 2010-01-01 Article (original research) 10.1017/S0269964810000057 24 3 405 422 18 Cambridge, United Kingdom Cambridge University Press eng 1803 Management Science and Operations Research1804 Statistics, Probability and Uncertainty2209 Industrial and Manufacturing Engineering2613 Statistics and Probability 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. C1 Provisional Code Non-UQ

 Document type: Journal Article Article (original research) School of Mathematics and Physics

 Versions Version Filter Type Sat, 21 Jan 2017, 08:06:37 EST Thu, 12 Oct 2017, 02:43:33 EST Filtered Full
Citation counts: Cited 0 times in Thomson Reuters Web of Science Article Cited 0 times in Scopus Article Search Google Scholar Fri, 07 Feb 2014, 20:10:29 EST by Radislav Vaisman on behalf of Scholarly Communication and Digitisation Service