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

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