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