Concentration inequalities on the multislice and for sampling without replacement

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$, 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.

References in corpus (8)

• Estimates of moments and tails of Gaussian chaoses
• Concentration inequalities for sampling without replacement
• Upper tails for triangles
• Transductive Rademacher Complexity and its Applications
• Higher order concentration for functions of weakly dependent random variables
• Concentration inequalities for bounded functionals via generalized log-Sobolev inequalities
• Modified log-Sobolev inequalities and two-level concentration
• FKN theorem for the multislice, with applications