How Monte Carlo Sampling Powers AI: From Basics to Acceptance-Rejection

MCMC Overview

From the name we can see MCMC consists of two MCs: Monte Carlo Simulation (MC) and Markov Chain (MC). To understand MCMC we first need to grasp Monte Carlo methods and Markov chains. This series will cover MCMC in three parts; this article focuses on Monte Carlo methods.

Introduction to Monte Carlo Methods

Monte Carlo was originally the name of a casino, reflecting its random simulation nature, similar to rolling dice. Early Monte Carlo methods were used to solve difficult summations or integrals. For example, an integral whose antiderivative is hard to obtain can be approximated by Monte Carlo simulation.

Assume the function graph is as shown:

A simple approximation samples a random point in the interval and uses its function value to represent the integral over that interval. Using a single point is crude; instead we can sample many points in the interval and use their mean to approximate the integral.

This approach implicitly assumes a uniform distribution over the interval, which is often unrealistic. If we know the true probability density function p(x) over the interval, we can weight the samples accordingly, leading to the general Monte Carlo formula. Thus the uniform case is a special case of a general probability distribution.

Probability Distribution Sampling

The key to Monte Carlo is obtaining the probability distribution p(x). Once we have p(x), we can draw samples from it and plug them into the Monte Carlo sum. Uniform distributions are easy to sample via linear congruential generators. Other common distributions (e.g., 2‑D normal) can be obtained by transforming uniform samples. Many libraries such as NumPy and scikit‑learn provide functions for these transformations. However, for uncommon distributions we cannot directly generate samples.

Acceptance‑Rejection Sampling

When the target distribution is uncommon, acceptance‑rejection sampling offers a solution. We choose a proposal distribution (e.g., a Gaussian) that is easy to sample and a constant M such that the target density is always below M times the proposal density. We then sample a point from the proposal, draw a uniform random number, and accept the sample if it falls under the scaled proposal curve; otherwise we reject it. Repeating this yields accepted samples that follow the target distribution.

This process uses a series of accept/reject decisions to simulate the desired probability distribution.

Monte Carlo Method Summary

Acceptance‑rejection sampling allows us to handle non‑standard distributions, but it may still be difficult to obtain samples for certain high‑dimensional or complex distributions. For example, for some 2‑D distributions we may only have conditional distributions, making acceptance‑rejection infeasible, and for high‑dimensional uncommon distributions finding a suitable proposal and constant M is challenging. The next article will introduce Markov chains, which help generate samples for such complex distributions.

Source

Liu Jianping Pinard https://www.cnblogs.com/pinard/p/6625739.html