A note on generating random variables with log-concave densities (Q433605)

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. In the Introduction of the paper, a small presentation of preliminary results about the black-box algorithm for construction of random variables, is realized. In 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. In 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.\) In 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. In Section 5 the log-concave densities in general are discussed. An estimation in explicit form of the density function is given. An algorithm which is based on this kind of density function is described. The idea of a generalization to the discrete case is discussed.