  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.
