{
  "id": "2010.16289",
  "version": "v1",
  "published": "2020-10-30T14:35:15.000Z",
  "updated": "2020-10-30T14:35:15.000Z",
  "title": "Concentration inequalities on the multislice and for sampling without replacement",
  "authors": [
    "Holger Sambale",
    "Arthur Sinulis"
  ],
  "categories": [
    "math.PR"
  ],
  "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\\H{o}s--R\\'{e}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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-10-30T14:35:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "concentration inequalities",
      "multislice",
      "talagrands convex distance inequality",
      "concentration results",
      "sub-gaussian right tail"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}