- 著者
- David Applegate
- タイトル
- Sampling, Integration, and Computing Volumes
- 日時
- December 1991
- 概要
- Sampling is a fundamental method for approximating answers that
cannot be directly computed.
Samples often need to be taken from a non-uniform distribution.
In this thesis, I present an algorithm to generate samples from
log-concave and nearly log-concave distributions.
This sampling algorithm is based on a biased random walk, and
the proof of correctness also provides bounds on the mixing time
of the Gibbs samples with the random sweep strategy.
To demonstrate the usefulness of sampling from log-concave
distrubutions, I use this algorithm to integrate log-concave
functions and to compute the volume of convex sets.
This resulting volume algorithm improves on the existing volume
algorithms due to Dyer, Frieze, and Kannan, and Lovasz and
Simonovits.
Samples generated by the sampling algorithm can also be used to
estimate marginal densities and as a tool for Bayesian
inference.
- カテゴリ
- CMUTR

Category: CMUTR
Institution: Department of Computer Science, Carnegie
Mellon University
Abstract: Sampling is a fundamental method for approximating answers that
cannot be directly computed.
Samples often need to be taken from a non-uniform distribution.
In this thesis, I present an algorithm to generate samples from
log-concave and nearly log-concave distributions.
This sampling algorithm is based on a biased random walk, and
the proof of correctness also provides bounds on the mixing time
of the Gibbs samples with the random sweep strategy.
To demonstrate the usefulness of sampling from log-concave
distrubutions, I use this algorithm to integrate log-concave
functions and to compute the volume of convex sets.
This resulting volume algorithm improves on the existing volume
algorithms due to Dyer, Frieze, and Kannan, and Lovasz and
Simonovits.
Samples generated by the sampling algorithm can also be used to
estimate marginal densities and as a tool for Bayesian
inference.
Number: CMU-CS-91-207
Bibtype: TechReport
Month: dec
Author: David Applegate
Title: Sampling, Integration, and Computing Volumes
Year: 1991
Address: Pittsburgh, PA
Super: @CMUTR