Concentration Inequalities on the Multislice and for Sampling Without Replacement

Sambale H, Sinulis A (2021)
Journal of Theoretical Probability .

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Abstract / Bemerkung
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) Erdos-Renyi 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), 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 theKolmogorov distance between the empirical measure and the true distribution of the sample.
Stichworte
Concentration of measure; Convex distance inequality; Erdos-Renyi; graphs; Multislice; Sampling without replacement
Erscheinungsjahr
2021
Zeitschriftentitel
Journal of Theoretical Probability
ISSN
0894-9840
eISSN
1572-9230
Page URI
https://pub.uni-bielefeld.de/record/2958892

Zitieren

Sambale H, Sinulis A. Concentration Inequalities on the Multislice and for Sampling Without Replacement. Journal of Theoretical Probability . 2021.
Sambale, H., & Sinulis, A. (2021). Concentration Inequalities on the Multislice and for Sampling Without Replacement. Journal of Theoretical Probability . https://doi.org/10.1007/s10959-021-01139-9
Sambale, H., and Sinulis, A. (2021). Concentration Inequalities on the Multislice and for Sampling Without Replacement. Journal of Theoretical Probability .
Sambale, H., & Sinulis, A., 2021. Concentration Inequalities on the Multislice and for Sampling Without Replacement. Journal of Theoretical Probability .
H. Sambale and A. Sinulis, “Concentration Inequalities on the Multislice and for Sampling Without Replacement”, Journal of Theoretical Probability , 2021.
Sambale, H., Sinulis, A.: Concentration Inequalities on the Multislice and for Sampling Without Replacement. Journal of Theoretical Probability . (2021).
Sambale, Holger, and Sinulis, Arthur. “Concentration Inequalities on the Multislice and for Sampling Without Replacement”. Journal of Theoretical Probability (2021).

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar