This article is cited in 2 papers

On two approaches to concentration for sampling without replacement

I. O. Tolstikhin

Max Planck Institute for Intelligent Systems

Abstract: 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.

Received: 26.01.2014

DOI: 10.4213/tvp5069

 English version: Theory of Probability and its Applications, 2017, 61:3, 462–481

Bibliographic databases:

• 
• 
• 
• 
•