Concentration inequalities for sampling without replacement

被引：73

作者：

Bardenet, Remi ^{[1
]}

Maillard, Odalric-Ambrym ^{[2
]}

机构：

[1] Univ Oxford, Dept Stat, Oxford OX1 3TG, England

[2] Technion Israel Inst Technol, Fac Elect Engn, IL-32000 Haifa, Israel

来源：

BERNOULLI | 2015年 / 21卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

Bernstein; concentration bounds; sampling without replacement; Serfling; PROBABILITY-INEQUALITIES;

D O I：

10.3150/14-BEJ605

中图分类号：

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

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Concentration inequalities quantify the deviation of a random variable from a fixed value. In spite of numerous applications, such as opinion surveys or ecological counting procedures, few concentration results are known for the setting of sampling without replacement from a finite population. Until now, the best general concentration inequality has been a Hoeffding inequality due to Serfling [Ann. Statist. 2 (1974) 39-48]. In this paper, we first improve on the fundamental result of Serfling [Ann. Statist. 2 (1974) 39-48], and further extend it to obtain a Bernstein concentration bound for sampling without replacement. We then derive an empirical version of our bound that does not require the variance to be known to the user.

引用

页码：1361 / 1385

页数：25

共 15 条

[1]

[Anonymous], 2009, LECT NOTES

[2] Exploration-exploitation tradeoff using variance estimates in multi-armed bandits [J].