Publication: Novel schemes for adaptive rejection sampling
Loading...
Identifiers
Publication date
2011-07
Defense date
2011-07-04
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
We address the problem of generating random samples from a target probability distribution, with density function πβ, using accept/reject methods. An "accept/reject sampler" (or, simply, a "rejection sampler") is an algorithm that first draws a random variate from a proposal distribution with density πΉ (where πΉ β πβ, in general) and then performs a test to determine whether the variate can be accepted as a sample from the target distribution or not. If we apply the algorithm repeatedly until we accept π times, then we obtain a collection of π independent and identically distributed (i.i.d.) samples from the distribution with density πβ. The goal of the present work is to devise and analyze adaptive rejection samplers that can be applied to generate i.i.d. random variates from the broadest possible class of probability distributions. Adaptive rejection sampling algorithms typically construct a sequence of proposal functions πΉβ, πΉβ,... πΉβ..., such that (a) it is easy to draw i.i.d. samples from them and (b) they converge, in some way, to the density πβ of the target probability distribution. When surveying the literature, it is simple to identify several such methods but virtually all of them present severe limitations in the class of target densities,πβ, for which they can be applied. The "standard" adaptive rejection sampler by Gilks and Wild, for instance, only works when πβ is strictly log-concave. Through Chapters 3, 4 and 5 we introduce a new methodology for adaptive rejection sampling that can be used with a broad family of target probability densities (including, e.g., multimodal functions) and subsumes Gilks and Wild's method as a particular case. We discuss several variations of the main algorithm that enable, e.g., sampling from some particularly "difficult" distributions (for instance, cases where πβ has log-convex tails and in nite support) or yield "automatic" software implementations using little analytical information about the target density πβ. Several numerical examples, including comparisons with some of the most relevant techniques in the literature, are also shown in Chapter 6. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
En este trabajo abordamos el problema de generar muestras aleatorias de una distribuciΓ³n de probabilidad objetivo, con densidad πβ , empleando mΓ©todos de aceptaciΓ³n/rechazo. En un algoritmo de aceptaciΓ³n/rechazo, primero se genera una realizaciΓ³n aleatoria de una distribuciΓ³n tentativa con densidad πΉ (donde πΉ β πβ , en general) y a continuaciΓ³n se realiza un test para determinar si la muestra se puede aceptar como proveniente de la distribuciΓ³n objetivo o no. Si se aplica el algoritmo repetidamente hasta aceptar π veces, obtenemos una colecciΓ³n de π muestras independientes y idΓ©nticamente distribuidas (i.i.d.) de la distribuciΓ³n con densidad πβ. El objetivo del trabajo es proponer y analizar nuevos m Γ©todos de aceptaciΓ³n/rechazo adaptativos que pueden ser aplicados para generar muestras i.i.d. de la clase mΓ‘s amplia posible de distribuciones de probabilidad. Los algoritmos de aceptaciΓ³n/rechazo adaptativos suelen construir una secuencia de funciones tentativas πΉβ, πΉβ,... πΉβ..., tales que (a) sea fΓ‘cil generar muestras i.i.d. a partir de ellas y (b) converjan, de manera adecuada, hacia la densidad πβ de la distribuciΓ³n objetivo. Al revisar la literatura, es sencillo identificar varios mΓ©todos de este tipo pero todos ellos presentan limitaciones importantes en cuanto a las clases de densidades objetivo a las que se pueden aplicar. El mΓ©todo original de Gilks y Wild, por ejemplo, sΓ³lo funciona si πβ es estrictamente log-cΓ³ncava. En los CapΓ tulos 3, 4 y 5 presentamos una nueva metodologΓa para muestreo adaptativo por aceptaciΓ³n/rechazo que se puede utilizar con una amplia clase de densidades de probabilidad objetivo (incluyendo, por ejemplo, funciones multimodales) y comprende al mΓ©todo de Gilks y Wild como un caso particular. Se discuten diversas variaciones del algoritmo principal que facilitan, por ejemplo, el muestreo de algunas distribuciones particularmente "difΓciles" (e.g., casos en los que πβ tiene colas log-convexas y con soporte infinito) o una implementaciΓ³n software prΓ‘cticamente "automΓ‘tica", en el sentido de que necesitamos poca informaciΓ³n analΓtica acerca de la funciΓ³n πβ. En el CapΓtulo 6 mostramos varios ejemplos numΓ©ricos, incluyendo comparaciones con algunas de las tΓ©cnicas mΓ‘as relevantes que se pueden encontrar en la literatura.
En este trabajo abordamos el problema de generar muestras aleatorias de una distribuciΓ³n de probabilidad objetivo, con densidad πβ , empleando mΓ©todos de aceptaciΓ³n/rechazo. En un algoritmo de aceptaciΓ³n/rechazo, primero se genera una realizaciΓ³n aleatoria de una distribuciΓ³n tentativa con densidad πΉ (donde πΉ β πβ , en general) y a continuaciΓ³n se realiza un test para determinar si la muestra se puede aceptar como proveniente de la distribuciΓ³n objetivo o no. Si se aplica el algoritmo repetidamente hasta aceptar π veces, obtenemos una colecciΓ³n de π muestras independientes y idΓ©nticamente distribuidas (i.i.d.) de la distribuciΓ³n con densidad πβ. El objetivo del trabajo es proponer y analizar nuevos m Γ©todos de aceptaciΓ³n/rechazo adaptativos que pueden ser aplicados para generar muestras i.i.d. de la clase mΓ‘s amplia posible de distribuciones de probabilidad. Los algoritmos de aceptaciΓ³n/rechazo adaptativos suelen construir una secuencia de funciones tentativas πΉβ, πΉβ,... πΉβ..., tales que (a) sea fΓ‘cil generar muestras i.i.d. a partir de ellas y (b) converjan, de manera adecuada, hacia la densidad πβ de la distribuciΓ³n objetivo. Al revisar la literatura, es sencillo identificar varios mΓ©todos de este tipo pero todos ellos presentan limitaciones importantes en cuanto a las clases de densidades objetivo a las que se pueden aplicar. El mΓ©todo original de Gilks y Wild, por ejemplo, sΓ³lo funciona si πβ es estrictamente log-cΓ³ncava. En los CapΓ tulos 3, 4 y 5 presentamos una nueva metodologΓa para muestreo adaptativo por aceptaciΓ³n/rechazo que se puede utilizar con una amplia clase de densidades de probabilidad objetivo (incluyendo, por ejemplo, funciones multimodales) y comprende al mΓ©todo de Gilks y Wild como un caso particular. Se discuten diversas variaciones del algoritmo principal que facilitan, por ejemplo, el muestreo de algunas distribuciones particularmente "difΓciles" (e.g., casos en los que πβ tiene colas log-convexas y con soporte infinito) o una implementaciΓ³n software prΓ‘cticamente "automΓ‘tica", en el sentido de que necesitamos poca informaciΓ³n analΓtica acerca de la funciΓ³n πβ. En el CapΓtulo 6 mostramos varios ejemplos numΓ©ricos, incluyendo comparaciones con algunas de las tΓ©cnicas mΓ‘as relevantes que se pueden encontrar en la literatura.
Description
Keywords
Random samples, Probability distribution, Rejection sampling