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

arXiv: https://arxiv.org/abs/2011.00901 · HTML: https://mlsanity.com/paper/2011.00901/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2020.

## Built on by (most cited first, 9 of 9)

- [Factor Analysis, Probabilistic Principal Component Analysis, Variational Inference, and Variational Autoencoder: Tutorial and Survey](https://mlsanity.com/paper/2101.00734/) (2021)
- [KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey](https://mlsanity.com/paper/2110.01858/) (2021)
- [Data Representativity for Machine Learning and AI Systems](https://mlsanity.com/paper/2203.04706/) (2022)
- [Spectral, Probabilistic, and Deep Metric Learning: Tutorial and Survey](https://mlsanity.com/paper/2201.09267/) (2022)
- [Restricted Boltzmann Machine and Deep Belief Network: Tutorial and Survey](https://mlsanity.com/paper/2107.12521/) (2021)
- [Generative Adversarial Networks and Adversarial Autoencoders: Tutorial and Survey](https://mlsanity.com/paper/2111.13282/) (2021)
- [Clustering large 3D volumes: A sampling-based approach](https://mlsanity.com/paper/2303.04188/) (2023)
- [DUA-D2C: Dynamic Uncertainty Aware Method for Overfitting Remediation in Deep Learning](https://mlsanity.com/paper/2411.15876/) (2024)
- [A Baseline Assessment for the Agentic Web Technology Stack](https://mlsanity.com/paper/2610.13703/) (2026)

## Abstract (arXiv)

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.