论文标题
碰撞估计器的浓度界限
Concentration Bounds for the Collision Estimator
论文作者
论文摘要
我们证明了自然碰撞估计器的浓度很强，该估计算出了IID样品中发生的碰撞数量。该估计器是用于均匀性测试和熵评估的算法的核心。 虽然先前的作品仅限于方差，但我们使用独立兴趣的优雅技术来界定较高的力矩并结论浓度属性。作为直接的推论，我们表明估算器自行实现高概率保证，并且不需要提高（又称中位数/多数派技巧）。
We prove a strong concentration result about the natural collision estimator, which counts the number of collisions that occur within an iid sample. This estimator is at the heart of algorithms used for uniformity testing and entropy assessment. While the prior works were limited to only variance, we use elegant techniques of independent interest to bounds higher moments and conclude concentration properties. As an immediate corollary we show that the estimator achieves high-probability guarantee on its own and there is no need for boosting (aka median/majority trick).
