On two approaches to concentration for sampling without replacement
Teoriâ veroâtnostej i ee primeneniâ, Tome 61 (2016) no. 3, pp. 464-488
Voir la notice de l'article provenant de la source Math-Net.Ru
This paper considers the concentration of values of functions of random variables sampled without replacement from a fixed finite set close to their expectations — a problem which is relevant to a variety of applications, including the transductive formulation of statistical learning theory. Apart from the review of known results, the paper studies two general approaches leading in many cases to sufficiently exact concentration inequalities. The first is based on the sub-Gaussian inequality of Bobkov [Ann. Probab., 32 (2004), pp. 2884–2907] for functions defined on a slice of the discrete cube. The second approach proposed by Hoeffding [J. Amer. Statist. Assoc., 58 (1963), pp. 13–30] reduces the problem to studying a sample of independent random variables.
Keywords:
concentration inequalities, empirical processes, choice without replacement.
@article{TVP_2016_61_3_a2,
author = {I. O. Tolstikhin},
title = {On two approaches to concentration for sampling without replacement},
journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
pages = {464--488},
publisher = {mathdoc},
volume = {61},
number = {3},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/TVP_2016_61_3_a2/}
}
I. O. Tolstikhin. On two approaches to concentration for sampling without replacement. Teoriâ veroâtnostej i ee primeneniâ, Tome 61 (2016) no. 3, pp. 464-488. http://geodesic.mathdoc.fr/item/TVP_2016_61_3_a2/