Rejection sampling

Summary

In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of exact simulation method. The method works for any distribution in \mathbb{R}^m with a density. Rejection sampling is based on the observation that to sample a random variable in one dimension, one can perform a uniformly random sampling of the two-dimensional Cartesian graph, and keep the samples in the region under the graph of its density function. Note that this property can be extended to N-dimension functions. Description To visualize the motivation behind rejection sampling, imagine graphing the density function of a random variable onto a large rectangular board and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now remove all of the darts that are outside the area under

Official source

https://en.wikipedia.org/wiki/Rejection_sampling

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related publications

Related people

Related units

Related concepts (13)

Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers (PRN) that follow a given probability distribution. Methods are typ

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use rando

In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as

Related concepts

Related courses (8)

Related courses

Related lectures (18)

Related lectures

Exact simulation of max-stable processes

Clément Dombry, Sebastian Engelke

Max-stable processes play an important role as models for spatial extreme events. Their complex structure as the pointwise maximum over an infinite number of random functions makes their simulation difficult. Algorithms based on finite approximations are often inexact and computationally inefficient. We present a new algorithm for exact simulation of a max-stable process at a finite number of locations. It relies on the idea of simulating only the extremal functions, that is, those functions in the construction of a max-stable process that effectively contribute to the pointwise maximum. We further generalize the algorithm by Dieker & Mikosch (2015) for Brown-Resnick processes and use it for exact simulation via the spectral measure. We study the complexity of both algorithms, prove that our new approach via extremal functions is always more efficient, and provide closed-form expressions for their implementation that cover most popular models for max-stable processes and multivariate extreme value distributions. For simulation on dense grids, an adaptive design of the extremal function algorithm is proposed.

Oxford University Press2016

EPFL2001

Some impulse radio UWB (IR-UWB) networks may allow concurrent transmissions without power control (for example MAC protocols that do not use power control, or co-exisiting, non-coordinated piconets). In such cases, it has been proposed to mitigate multi-user interference (MUI) at the physical layer, but existing proposals for interference mitigation do not account for the multipath nature of UWB channels. We address this problem and propose a receiver that employs a combination of statistical interference modeling and thresholding to mitigate MUI. We find that in a multipath environment the proposed receiver significantly outperforms existing receiver designs that either completely neglect the effect of MUI or only use a simple threshold to reject samples from interfering users. Further, in contrast to successive interference cancellation schemes, our receiver does not require active decoding of each interferer. Thus there is no need to synchronize the receiver with all the interfering users, which would be impractical in an IR-UWB system that is likely to be run in ad hoc mode. To model MUI we consider a hidden Markov model (HMM) and a Gaussian mixture model (GMM). We find that the HMM models interference better than the GMM. However, the resulting performance difference is not huge and comes at the cost of increased receiver complexity.

2006