Concentration Inequalities on the Multislice and for Sampling Without Replacement

Holger Sambale () and Arthur Sinulis ()
Additional contact information
Holger Sambale: Universität Bielefeld
Arthur Sinulis: Universität Bielefeld

Journal of Theoretical Probability, 2022, vol. 35, issue 4, 2712-2737

Abstract: Abstract We present concentration inequalities on the multislice which are based on (modified) log-Sobolev inequalities. This includes bounds for convex functions and multilinear polynomials. As an application, we show concentration results for the triangle count in the G(n, M) Erdős–Rényi model resembling known bounds in the G(n, p) case. Moreover, we give a proof of Talagrand’s convex distance inequality for the multislice. Interpreting the multislice in a sampling without replacement context, we furthermore present concentration results for n out of N sampling without replacement. Based on a bounded difference inequality involving the finite-sampling correction factor $$1 - (n / N)$$ 1 - ( n / N ) , we present an easy proof of Serfling’s inequality with a slightly worse factor in the exponent, as well as a sub-Gaussian right tail for the Kolmogorov distance between the empirical measure and the true distribution of the sample.

Keywords: Concentration of measure; Convex distance inequality; Erdős–Rényi graphs; Multislice; Sampling without replacement; 60E15; 62D05 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10959-021-01139-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:35:y:2022:i:4:d:10.1007_s10959-021-01139-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-021-01139-9

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().