Concentration Inequalities on the Multislice and for Sampling Without Replacement

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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 449.32 KB
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
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Universität Bielefeld im Rahmen des DEAL-Vertrags gefördert.
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, Holger, and Sinulis, Arthur. 2021. “Concentration Inequalities on the Multislice and for Sampling Without Replacement”. Journal of Theoretical Probability .
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).
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2022-10-17T06:31:53Z
MD5 Prüfsumme
be2e3e85cba5d097349c9598274088d8

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Suchen in

Google Scholar