Practical Probabilistic Programming

Chapter 11. Sampling algorithms

This chapter covers

• The basic principles of sampling algorithms
• The importance sampling algorithm
• Markov chain Monte Carlo (MCMC) algorithm
• The Metropolis-Hastings variant of MCMC

This chapter continues the theme of the previous chapter, presenting some of the main algorithms used in probabilistic programming inference. Whereas chapter 10 focused on factored algorithms such as variable elimination and belief propagation, this chapter looks at sampling algorithms that answer queries by generating possible states of variables drawn from the probability distribution defined by the program. In particular, the chapter presents two useful algorithms: importance sampling and Markov chain Monte Carlo (MCMC).