Sampling algorithms for estimating the mean of bounded random variables

被引：32

作者：

Cheng, J ^{[1
]}

机构：

[1] Univ Pittsburgh, Sch Informat Sci, Decis Syst Lab, Pittsburgh, PA 15260 USA

来源：

COMPUTATIONAL STATISTICS | 2001年 / 16卷 / 01期

关键词：

algorithm; sampling; Monte Carlo estimation; confidence intervals;

D O I：

10.1007/s001800100049

中图分类号：

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

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We show two distribution-independent algorithms to estimate the mean of bounded random variables, one with the knowledge of variance, the other without. These algorithms guarantee that the estimate is within the desired precision with an error probability less than or equal to the requirement. Some simplified stopping rules are also given.

引用

页码：1 / 23

页数：23

共 13 条

[1] PROBABILITY-INEQUALITIES FOR SUM OF INDEPENDENT RANDOM-VARIABLES [J].

BENNETT, G .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1962, 57 (297) :33-&

[2]

BERNSTEIN SN, 1927, THEORY PROBABILITY

[3] LOWER BOUNDS FOR SAMPLING ALGORITHMS FOR ESTIMATING THE AVERAGE [J].

CANETTI, R ;

EVEN, G ;

GOLDREICH, O .

INFORMATION PROCESSING LETTERS, 1995, 53 (01) :17-25

[4] AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks [J].

Cheng, J ;

Druzdzel, MJ .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 13 :155-188

[5] An optimal algorithm for Monte Carlo estimation [J].

Dagum, P ;

Karp, R ;

Luby, M ;

Ross, S .

SIAM JOURNAL ON COMPUTING, 2000, 29 (05) :1484-1496

[6] APPROXIMATING PROBABILISTIC INFERENCE IN BAYESIAN BELIEF NETWORKS [J].

DAGUM, P ;

CHAVEZ, RM .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1993, 15 (03) :246-255

[7] A BAYESIAN-ANALYSIS OF SIMULATION ALGORITHMS FOR INFERENCE IN BELIEF NETWORKS [J].

DAGUM, P ;

HORVITZ, E .

NETWORKS, 1993, 23 (05) :499-516

[8] An optimal approximation algorithm for Bayesian inference [J].

Dagum, P ;

Luby, M .

ARTIFICIAL INTELLIGENCE, 1997, 93 (1-2) :1-27

[9] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[10] A MONTE-CARLO ALGORITHM FOR ESTIMATING THE PERMANENT [J].

KARMARKAR, N ;

KARP, R ;

LIPTON, R ;

LOVASZ, L ;

LUBY, M .

SIAM JOURNAL ON COMPUTING, 1993, 22 (02) :284-293

← 1 2 →