×

Log-Sobolev inequalities and sampling from log-concave distributions. (English) Zbl 0931.68140

Summary: We consider the problem of sampling according to a distribution with log-concave density \(F\) over a convex body \(K\subseteq \mathbb{R}^n\). The sampling is done using a biased random walk and we give improved polynomial upper bounds on the time to get a sample point with distribution close to \(F\).

MSC:

68W05 Nonnumerical algorithms
60G50 Sums of independent random variables; random walks
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] APPLEGATE, D. and KANNAN, R. 1991. Sampling and integration of log-concave functions. In Proceedings of the 23rd Annual ACM Sy mposium on Theory of Computing 156 163.
[2] ACM, New York.
[3] DIACONIS, P. and SALOFF-COSTE, L. 1998. Logarithmic Sobolev inequalities for finite Markov chains. Unpublished manuscript. · Zbl 0867.60043
[4] FRIEZE, A. M., KANNAN, R. and POLSON, N. 1994. Sampling from log-concave distributions. Ann. Appl. Probab. 4 812 837. · Zbl 0813.60060
[5] KANNAN, R., LOVASZ, L. and SIMONOVITS, M. 1998. Random walks and an O* n volume álgorithm for convex bodies. Random Structures Algorithms.
[6] LOVASZ, L. and SIMONOVITS, M. 1990. Mixing rate of Markov chains, an isoperimetric ínequality and computing the volume. In Proceeding of the 31st Annual IEEE Sy mposium on Foundations of Computer Science 346 355. IEEE, New York.
[7] LOVASZ, L. and SIMONOVITS, M. 1993. Random walks in a convex body and an improved \' volume algorithm. Random Structures Algorithms 4 359 412. · Zbl 0788.60087
[8] METROPOLIS, N., ROSENBERG, ROSENBLUTH, TELLER and TELLER 1953. Equation of state calculation by fast computing machines. J. Chemical physics 21 1087 1092.
[9] SINCLAIR, A. J. and JERRUM, M. R. 1989. Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82 93 133. · Zbl 0668.05060
[10] PITTSBURGH, PENNSy LVANIA 15213 PITTSBURGH, PENNSy LVANIA 15213
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.