SAMPLING FROM LOG-CONCAVE DISTRIBUTIONS

被引：39

作者：

Frieze, Alan ^{[1
]}

Kannan, Ravi ^{[2
,3
]}

Polson, Nick ^{[4
]}

机构：

[1] Carnegie Mellon Univ, Dept Math, Pittsburgh, PA 15213 USA

[2] BELLCORE, Morristown, NJ 07962 USA

[3] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA

[4] Univ Chicago, Grad Sch Business, Chicago, IL 60637 USA

来源：

ANNALS OF APPLIED PROBABILITY | 1994年 / 4卷 / 03期

关键词：

Sampling; random walk; log-concave functions;

D O I：

10.1214/aoap/1177004973

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We consider the problem of sampling according to a distribution with log-concave density F over a convex body K subset of R-n. The sampling is dine using a biased random walk, and polynomial upper bounds on the time to get a sample point with disribution close to F.

引用

页码：812 / 837

页数：26

共 10 条

[1]

Anderson WN, 1985, LINEAR MULTILINEAR A, V18, P141, DOI DOI 10.1080/03081088508817681

[2]

Applegate David, 1991, P 23 ANN ACM S THEOR, P156, DOI DOI 10.1145/103418.103439

[3] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES [J].

DYER, M ;

FRIEZE, A ;

KANNAN, R .

JOURNAL OF THE ACM, 1991, 38 (01) :1-17

[4]

Fill J. A, 1991, ANN APPL PROBAB, P62

[5]

KANNAN R., 1993, RANDOM SAMPLIN UNPUB

[6]

Lovasz L., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P346, DOI 10.1109/FSCS.1990.89553

[7]

LOVASZ L., 1993, RANDOM STRU IN PRESS

[8] EQUATION OF STATE CALCULATIONS BY FAST COMPUTING MACHINES [J].

METROPOLIS, N ;

ROSENBLUTH, AW ;

ROSENBLUTH, MN ;

TELLER, AH ;

TELLER, E .

JOURNAL OF CHEMICAL PHYSICS, 1953, 21 (06) :1087-1092

[9]

MIHAIL M, 1989, THESIS HARVARD U

[10]

TIERNEY L., 1994, ANN STAT IN PRESS

← 1 →