论文标题
多层的浓度不平等和无需替代的采样
Concentration inequalities on the multislice and for sampling without replacement
论文作者
论文摘要
我们提出了基于（修改的）对数 - 贝贝尔的不等式的多层质量的浓度不平等。这包括凸函数和多项式多项式的边界。作为一个应用程序，我们显示了三角计数的集中度结果（n，m）$erdős--rényi模型类似于$ g（n，p）$案例中已知界限。此外，我们给出了Talagrand对多层的凸距离不平等的证明。 在没有替换上下文的情况下，在采样中解释多层，我们此外，我们的当前浓度结果是$ n $ n $采样的$ n $，而无需更换。基于涉及有限采样校正因子$ 1- N/N $的有界差异不平等，我们简单地证明了Serfling的不平等现象，指数中的因素稍差，以及kolmogorov的次高斯右尾部，用于kolmogorov距离的经验度量和样品真实分布之间的距离。
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.
