A note on generating random variables with log-concave densities
type: Item
instance of: scholarly article
title: A note on generating random variables with log-concave densities
zbMATH Open document ID: 1255.65016
published in: Statistics \& Probability Letters
publication date: 2012-07-05T00:00:00Z
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 65C35
Mathematics Subject Classification ID: 65C50
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 68U20
zbMATH DE Number: 6053361
zbMATH Keywords: black-box style rejection algorithm
zbMATH Keywords: log-concave density function
zbMATH Keywords: random numbers
zbMATH Keywords: mode
zbMATH Keywords: binary search
zbMATH Keywords: rejection algorithm
zbMATH Keywords: random variate generation
zbMATH Keywords: simulation
zbMATH Keywords: Monte Carlo method
zbMATH Keywords: expected time analysis
author: Luc Devroye
reviewed by: Vassil Grozdanov
describes a project that uses: AS 287
MaRDI profile type: Publication
full work available at URL: j.spl.2012.01.022
OpenAlex ID: W2086016443
cites work: A simple algorithm for generating random variates with a log-concave density
cites work: Q3723577
cites work: Adaptive Rejection Sampling for Gibbs Sampling
cites work: Adaptive Rejection Metropolis Sampling within Gibbs Sampling
cites work: Q4435446
DOI: 10.1016/J.SPL.2012.01.022
review text: The black-box style rejection algorithm is a tool for generation of random variables. In this small paper a black-box style rejection algorithm that is valid for generating random variables with any log-concave density with known mode is considered. It is shown that when the density is only known up to a constant factor, this method is no longer applicable.NEWLINENEWLINEIn the Introduction of the paper, a small presentation of preliminary results about the black-box algorithm for construction of random variables, is realized.NEWLINENEWLINEIn Section 2 a nonincreasing nonnegative log-concave function on \([0, \infty)\) is considered. For given reals \(0 \leq a < b < \infty\) the equation \(g(x)\) of the line through the points \((a, \log f(a))\) and \((b, \log f(b))\) is shown. Two integrals from the function \(\text{exp}(g(x))\) are calculated.NEWLINENEWLINEIn Section 3 the log-concave density on the positive half-line is considered. To construct the mathematical base of the rejection algorithm, it is assumed that the mode \(m\) is equals to zero. An estimation of the density function of the rejection algorithm is shown. The construction of a random variable which is based on the rejection algorithm is practically realized. This permits to give the details of the rejection algorithm. It is proved that the expected number of the iterations in the rejection algorithm is bounded by 5, uniformly over all log-concave densities on \({\mathbb R}^{+}\) with mode \(m=0.\)NEWLINENEWLINEIn Section 4 the binary search for the parameter \(a\) of the rejection algorithm is organized in a such a manner that the one-time set-up cost of this algorithm to be small. The order \({\mathcal O}(1) + | \log_{2}R|\) where \(R\) is the multiplicative costant of the density function of the number of steps of the rejection algorithm is shown.NEWLINENEWLINEIn Section 5 the log-concave densities in general are discussed. An estimation in explicit form of the density function is given. An algorit…
description: scientific article; zbMATH DE number 6053361