How to generate uniform samples on discrete sets using the splitting method. (English) Zbl 1196.60134
Summary: 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 mechanism-can 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.
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 mechanism-can 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.
MSC:
| 60J22 | Computational methods in Markov chains |
References:
| [1] | Ross, Simulation (2006) · Zbl 1111.65008 |
| [2] | DOI: 10.1145/1225275.1225280 · Zbl 1281.62085 · doi:10.1145/1225275.1225280 |
| [3] | Gryazina, Annals of Operations Research (2010) |
| [4] | DOI: 10.1239/jap/1245676098 · Zbl 1168.65008 · doi:10.1239/jap/1245676098 |
| [5] | Garvels (2000) |
| [6] | DOI: 10.1287/opre.32.6.1296 · Zbl 0552.65004 · doi:10.1287/opre.32.6.1296 |
| [7] | DOI: 10.1023/A:1010091220143 · Zbl 0941.65061 · doi:10.1023/A:1010091220143 |
| [8] | DOI: 10.1002/9780470230381 · Zbl 1147.68831 · doi:10.1002/9780470230381 |
| [9] | Asmussen, Stochastic simulation: Algorithms and analyses (2007) |
| [10] | Rubinstein, The cross-entropy method: A unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning (2004) · Zbl 1140.90005 |
| [11] | DOI: 10.1007/s11009-009-9126-6 · Zbl 1187.65001 · doi:10.1007/s11009-009-9126-6 |
| [12] | DOI: 10.1007/s11009-008-9101-7 · Zbl 1177.65012 · doi:10.1007/s11009-008-9101-7 |
| [13] | DOI: 10.1007/s11009-008-9073-7 · Zbl 1293.65004 · doi:10.1007/s11009-008-9073-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
