97-07-01.ley
A Rejection Technique for Sampling from
Log-Concave Multivariate Distributions
Abstract
Different universal methods (also called automatic or black-box
methods) have been suggested to sample from univariate log-concave
distributions. The description of a suitable universal generator for
multivariate distributions in arbitrary dimensions has not been
published up to now. The new algorithm is based on the method of
transformed density rejection. To construct a hat function for the
rejection algorithm the multivariate density is tranformed by a
proper transformation T into a concave function (in the case of
log-concave density T(x) = log(x).)
Then it is possible to construct a dominating function by taking the
minimum of several tangent hyperplanes which are transformed back by
$T^{-1}$ into the original scale.
The domains of different pieces of the hat function are polyhedra in
the multivariate case.
Although this method can be shown to work, it is too
slow and complicated in higher dimensions. In this paper we split
the $R^n$ into
simple cones. The hat function is constructed piecewise on each of
the cones by tangent hyperplanes. The resulting function is not
continuous any more and the rejection constant is bounded from below
but the setup and the generation remains quite fast in higher
dimensions, e.g. n=8.
The paper describes the details how this main idea can be used to
construct algorithm TDRMV that generates random tuples
from multivariate log-concave distribution with a computable density.
Although the developed algorithm is not a real black box method it is
adjustable for a large class of log-concave densities.
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
General Terms:
Algorithms
Key Words:
Rejection method, multivariate log-concave distributions, universal method
Download Preprint
© ACM, (1998). This is the author's version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in
Trans. Model. Comput. Simul. 8(3), 254-280.
http://doi.acm.org/10.1145/290274.290287
Paper
Josef.Leydold@statistik.wu-wien.ac.at