Teoriya Veroyatnostei i ee Primeneniya
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Guidelines for authors Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Teor. Veroyatnost. i Primenen.: Year: Volume: Issue: Page: Find

 Teor. Veroyatnost. i Primenen., 2016, Volume 61, Issue 3, Pages 464–488 (Mi tvp5069)

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.

 Funding Agency Grant Number Russian Foundation for Basic Research 14-07-00847_à

DOI: https://doi.org/10.4213/tvp5069

Full text: PDF file (322 kB)
References: PDF file   HTML file

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

Bibliographic databases:

Citation: I. O. Tolstikhin, “On two approaches to concentration for sampling without replacement”, Teor. Veroyatnost. i Primenen., 61:3 (2016), 464–488; Theory Probab. Appl., 61:3 (2017), 462–481

Citation in format AMSBIB
\Bibitem{Tol16} \by I.~O.~Tolstikhin \paper On two approaches to concentration for sampling without replacement \jour Teor. Veroyatnost. i Primenen. \yr 2016 \vol 61 \issue 3 \pages 464--488 \mathnet{http://mi.mathnet.ru/tvp5069} \crossref{https://doi.org/10.4213/tvp5069} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3626458} \zmath{https://zbmath.org/?q=an:1376.60047} \elib{https://elibrary.ru/item.asp?id=27485081} \transl \jour Theory Probab. Appl. \yr 2017 \vol 61 \issue 3 \pages 462--481 \crossref{https://doi.org/10.1137/S0040585X97T988277} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000412117600006} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85030319068}