Fast Sequential Monte Carlo Methods for Counting and Optimization

A comprehensive account of the theory and application of Monte Carlo methods Based on years of research in efficient Monte Carlo methods for estimation of rare-event probabilities, counting problems, and combinatorial optimization, Fast Sequential Monte Carlo Methods for Counting and Optimization is a complete illustration of fast sequential Monte Carlo techniques. The book provides an accessible overview of current work in the field of Monte Carlo methods, specifically sequential Monte Carlo techniques, for solving abstract counting and optimization problems. Written by authorities in the field, the book places emphasis on cross-entropy, minimum cross-entropy, splitting, and stochastic enumeration. Focusing on the concepts and application of Monte Carlo techniques, Fast Sequential Monte Carlo Methods for Counting and Optimization includes: Detailed algorithms needed to practice solving real-world problems Numerous examples with Monte Carlo method produced solutions within the 1-2% limit of relative error A new generic sequential importance sampling algorithm alongside extensive numerical results An appendix focused on review material to provide additional background information Fast Sequential Monte Carlo Methods for Counting and Optimization is an excellent resource for engineers, computer scientists, mathematicians, statisticians, and readers interested in efficient simulation techniques. The book is also useful for upper-undergraduate and graduate-level courses on Monte Carlo methods.

A comprehensive account of the theory and application of Monte Carlo methodsBased on years of research in efficient Monte Carlo methods for estimation of rare-event probabilities, counting problems, and combinatorial optimization, Fast Sequential Monte Carlo Methods for Counting and Optimization is a complete illustration of fast sequential Monte Carlo techniques. The book provides an accessible overview of current work in the field of Monte Carlo methods, specifically sequential Monte Carlo techniques, for solving abstract counting and optimization problems.Written by authorities in the field, the book places emphasis on cross-entropy, minimum cross-entropy, splitting, and stochastic enumeration. Focusing on the concepts and application of Monte Carlo techniques, Fast Sequential Monte Carlo Methods for Counting and Optimization includes:* Detailed algorithms needed to practice solving real-world problems* Numerous examples with Monte Carlo method produced solutions within the 1-2% limit of relative error* A new generic sequential importance sampling algorithm alongside extensive numerical results* An appendix focused on review material to provide additional background informationFast Sequential Monte Carlo Methods for Counting and Optimization is an excellent resource for engineers, computer scientists, mathematicians, statisticians, and readers interested in efficient simulation techniques. The book is also useful for upper-undergraduate and graduate-level courses on Monte Carlo methods.

Preface xi1. Introduction to Monte Carlo Methods 12. Cross-Entropy Method 62.1. Introduction 62.2. Estimation of Rare-Event Probabilities 72.3. Cross-Entrophy Method for Optimization 182.3.1. The Multidimensional 0/1 Knapsack Problem 212.3.2. Mastermind Game 232.3.3. Markov Decision Process and Reinforcement Learning 252.4. Continuous Optimization 312.5. Noisy Optimization 332.5.1. Stopping Criterion 353. Minimum Cross-Entropy Method 373.1. Introduction 373.2. Classic MinxEnt Method 393.3. Rare Events and MinxEnt 433.4. Indicator MinxEnt Method 473.4.1. Connection between CE and IME 513.5. IME Method for Combinatorial Optimization 523.5.1. Unconstrained Combinatorial Optimization 523.5.2. Constrained Combinatorial Optimization: The Penalty Function Approach 544. Splitting Method for Counting and Optimization 564.1. Background 564.2. Quick Glance at the Splitting Method 584.3. Splitting Algorithm with Fixed Levels 644.4. Adaptive Splitting Algorithm 684.5. Sampling Uniformly on Discrete Regions 744.6. Splitting Algorithm for Combinatorial Optimization 754.7. Enhanced Splitting Method for Counting 764.7.1. Counting with the Direct Estimator 764.7.2. Counting with the Capture-Recapture Method 774.8. Application of Splitting to Reliability Models 794.8.1. Introduction 794.8.2. Static Graph Reliability Problem 824.8.3. BMC Algorithm for Computing S(Y) 844.8.4. Gibbs Sampler 854.9. Numerical Results with the Splitting Algorithms 864.9.1. Counting 874.9.2. Combinatorial Optimization 1014.9.3. Reliability Models 1024.10. Appendix: Gibbs Sampler 1045. Stochastic Enumeration Method 1065.1. Introduction 1065.2. OSLA Method and Its Extensions 1105.2.1. Extension of OSLA: nSLA Method 1125.2.2. Extension of OSLA for SAW: Multiple Trajectories 1155.3. SE Method 1205.3.1. SE Algorithm 1205.4. Applications of SE 1275.4.1. Counting the Number of Trajectories in a Network 1275.4.2. SE for Probabilities Estimation 1315.4.3. Counting the Number of Perfect Matchings in a Graph 1325.4.4. Counting SAT 1355.5. Numerical Results 1365.5.1. Counting SAW 1375.5.2. Counting the Number of Trajectories in a Network 1375.5.3. Counting the Number of Perfect Matchings in a Graph 1405.5.4. Counting SAT 1435.5.5. Comparison of SE with Splitting and SampleSearch 146A. Additional Topics 148A.1. Combinatorial Problems 148A.1.1. Counting 149A.1.2. Combinatorial Optimization 154A.2. Information 162A.2.1. Shannon Entropy 162A.2.2. Kullback-Leibler Cross-Entropy 163A.3. Efficiency of Estimators 164A.3.1. Complexity 165A.3.2. Complexity of Randomized Algorithms 166Bibliography 169Abbreviations and Acronyms 177List of Symbols 178Index 181