Sampling Algorithms, from Survey Sampling to Monte Carlo Methods:\n Tutorial and Literature Review

Benyamin Ghojogh, Hadi Nekoei, Aydin Ghojogh, Fakhri Karray, Mark CrowleyarXiv 2020 · DOI · arXiv

Abstract

This paper is a tutorial and literature review on sampling algorithms. We have two main types of sampling in statistics. The first type is survey sampling which draws samples from a set or population. The second type is sampling from probability distribution where we have a probability density or mass function. In this paper, we cover both types of sampling. First, we review some required background on mean squared error, variance, bias, maximum likelihood estimation, Bernoulli, Binomial, and Hypergeometric distributions, the Horvitz-Thompson estimator, and the Markov property. Then, we explain the theory of simple random sampling, bootstrapping, stratified sampling, and cluster sampling. We also briefly introduce multistage sampling, network sampling, and snowball sampling. Afterwards, we switch to sampling from distribution. We explain sampling from cumulative distribution function, Monte Carlo approximation, simple Monte Carlo methods, and Markov Chain Monte Carlo (MCMC) methods. For simple Monte Carlo methods, whose iterations are independent, we cover importance sampling and rejection sampling. For MCMC methods, we cover Metropolis algorithm, Metropolis-Hastings algorithm, Gibbs sampling, and slice sampling. Then, we explain the random walk behaviour of Monte Carlo methods and more efficient Monte Carlo methods, including Hamiltonian (or hybrid) Monte Carlo, Adler's overrelaxation, and ordered overrelaxation. Finally, we summarize the characteristics, pros, and cons of sampling methods compared to each other. This paper can be useful for different fields of statistics, machine learning, reinforcement learning, and computational physics.

Introduction

In statistics and machine learning, the term "sampling" is often overloaded. A social scientist "samples" a neighborhood to estimate average income, while a physicist "samples" a Boltzmann distribution to simulate particle behavior. These two worlds—survey sampling and distribution sampling—are frequently taught in isolation despite sharing deep mathematical roots. This paper addresses this fragmentation by providing a pedagogical review that covers the "why" and "how" of both fields, serving as a mathematical "Rosetta Stone" for researchers.

Survey Sampling

Survey sampling involves selecting a subset of items from a finite population to make inferences about the whole. The paper categorizes these methods based on how the population is partitioned and selected.

  • Simple Random Sampling (SRS) & Bootstrapping: These are the foundational methods of drawing with and without replacement.
  • Stratified vs. Cluster Sampling: These techniques involve dividing the population into groups. In stratified sampling, the population is divided into homogeneous groups (strata), and samples are taken from every stratum to reduce variance. In cluster sampling, the population is divided into heterogeneous groups (clusters) that ideally represent the whole population; a few clusters are then randomly selected for full sampling to increase logistical efficiency.
Visual comparison of (a) Population, (b) Cluster Sampling, and (c) Stratified Sampling.
  • Advanced Methods: The paper also touches upon multistage, network, and snowball sampling for more complex population structures.

Monte Carlo Methods

Monte Carlo (MC) methods shift the focus to drawing samples from a probability distribution rather than a fixed set.

Simple Monte Carlo

Simple MC methods generate independent iterations to estimate expectations:

  • Importance Sampling: Uses a proposal distribution to estimate expectations of a target distribution.
  • Rejection Sampling: Uses an upper-bound "envelope" function to accept or reject candidates.

Markov Chain Monte Carlo (MCMC)

MCMC methods generate dependent samples where each draw depends on the previous one, forming a Markov Chain. Key algorithms include the Metropolis-Hastings algorithm and Gibbs Sampling. The paper provides a clear proof that Gibbs sampling is a specific version of Metropolis-Hastings where the proposal is always accepted.

Efficient Exploration

Simple MCMC algorithms often suffer from "random walk" behavior, where exploration is slow and inefficient in high dimensions. Hamiltonian Monte Carlo (HMC) overcomes this by treating the probability density as a landscape and the sampler as a particle with momentum. Using gradient information, HMC changes the exploration complexity from quadratic to linear, making it vastly superior for high-dimensional problems.

Key Insights

  • Variance Reduction: Stratified sampling is mathematically guaranteed to be better than (or equal to) simple random sampling if the chosen strata have different means, effectively "canceling out" the variance between groups.
  • The Random Walk Penalty: Simple Metropolis algorithms have a quadratic runtime complexity relative to the range of the data. To move a distance $L$ with a step size $\delta$, roughly $(L/\delta)^2$ steps are required.
  • The Horvitz-Thompson Estimator: The paper proves the unbiasedness of this foundational tool for weighting samples when inclusion probabilities vary.

Conclusion

This review serves as an essential primer for anyone entering fields like reinforcement learning, computational physics, or advanced Bayesian inference. While it covers a vast landscape, the authors note that hyperparameter tuning for advanced methods like HMC remains a significant challenge in extremely high-dimensional spaces.

Summary updated

Abstract

This paper is a tutorial and literature review on sampling algorithms. We\nhave two main types of sampling in statistics. The first type is survey\nsampling which draws samples from a set or population. The second type is\nsampling from probability distribution where we have a probability density or\nmass function. In this paper, we cover both types of sampling. First, we review\nsome required background on mean squared error, variance, bias, maximum\nlikelihood estimation, Bernoulli, Binomial, and Hypergeometric distributions,\nthe Horvitz-Thompson estimator, and the Markov property. Then, we explain the\ntheory of simple random sampling, bootstrapping, stratified sampling, and\ncluster sampling. We also briefly introduce multistage sampling, network\nsampling, and snowball sampling. Afterwards, we switch to sampling from\ndistribution. We explain sampling from cumulative distribution function, Monte\nCarlo approximation, simple Monte Carlo methods, and Markov Chain Monte Carlo\n(MCMC) methods. For simple Monte Carlo methods, whose iterations are\nindependent, we cover importance sampling and rejection sampling. For MCMC\nmethods, we cover Metropolis algorithm, Metropolis-Hastings algorithm, Gibbs\nsampling, and slice sampling. Then, we explain the random walk behaviour of\nMonte Carlo methods and more efficient Monte Carlo methods, including\nHamiltonian (or hybrid) Monte Carlo, Adler's overrelaxation, and ordered\noverrelaxation. Finally, we summarize the characteristics, pros, and cons of\nsampling methods compared to each other. This paper can be useful for different\nfields of statistics, machine learning, reinforcement learning, and\ncomputational physics.\n
BibTeX
@misc{ghojogh2020sampling,
  author = {Benyamin Ghojogh and Hadi Nekoei and Aydin Ghojogh and Fakhri Karray and Mark Crowley},
  title = {{Sampling Algorithms, from Survey Sampling to Monte Carlo Methods:\textbackslash\{\}n Tutorial and Literature Review}},
  year = {2020},
  eprint = {2011.00901},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.00901},
}
Figure