Tirer selon une distribution simple et conserver les points qui tombent sous la distribution cible.L'échantillonnage par rejet est une méthode de Monte Carlo simple pour générer des échantillons à partir d'une distribution de probabilité cible lorsque l'échantillonnage direct est difficile. Elle consiste à échantillonner à partir d'une distribution de proposition plus simple qui recouvre la distribution cible, puis à accepter ou rejeter chaque échantillon en fonction d'un test aléatoire. Les échantillons acceptés suivent exactement la distribution cible. C'est un algorithme fondamental en physique computationnelle et en statistiques, souvent utilisé comme brique de base pour des méthodes plus sophistiquées comme les chaînes de Markov Monte Carlo.
La méthode a été décrite par John von Neumann en 1951 dans un article sur diverses techniques de génération de nombres aléatoires, bien que des idées similaires soient apparues plus tôt dans la littérature statistique.
Étant donné une distribution cible p(x) et une distribution de proposition q(x) telles que p(x) ≤ M·q(x) pour une constante M, on tire un candidat x selon q(x) et un nombre aléatoire uniforme u dans [0,1]. On accepte x si u < p(x)/(M·q(x)), sinon on rejette et on recommence. Les échantillons acceptés sont distribués selon p(x). L'efficacité dépend du rapport des aires sous p et M·q ; si M est trop grand, de nombreux échantillons sont rejetés, ce qui gaspille du calcul. La méthode fonctionne le mieux lorsque q est une bonne approximation de p.
Utilisée en physique des particules pour générer des événements aléatoires selon des sections efficaces différentielles complexes, et en statistique bayésienne pour échantillonner des distributions a posteriori lorsque la constante de normalisation est inconnue.
L'échantillonnage par rejet est également connu sous le nom de « méthode acceptation-rejet » et est un ingrédient clé du célèbre algorithme de Metropolis-Hastings, qui le généralise pour traiter des problèmes en haute dimension.
