标题： 带权无放回抽样 显示英文标题

标题： Weighted sampling without replacement

摘要： 比较均匀抽样有放回和无放回的浓度性质有着悠久的历史，可以追溯到Hoeffding（1963）的先驱工作。 本文简短的目的是利用两种样本之间的耦合，将这种比较扩展到非均匀权重的情况。 当项目的权重与其值按相同顺序排列时，我们证明了累积值的诱导耦合是一个次鞅耦合。 作为结果，已知适用于有放回抽样的强大Chernoff型上尾估计自动转移到无放回抽样的情况。 对于一般权重，我们使用相同的耦合建立了次高斯浓度不等式。 我们还构建了另一个鞅耦合，使我们能够回答Luh和Pippenger（2014）在不同替换数的Polya瓮抽样中提出的问题。 显示英文摘要

摘要： Comparing concentration properties of uniform sampling with and without replacement has a long history which can be traced back to the pioneer work of Hoeffding (1963). The goal of this short note is to extend this comparison to the case of non-uniform weights, using a coupling between the two samples. When the items' weights are arranged in the same order as their values, we show that the induced coupling for the cumulative values is a submartingale coupling. As a consequence, the powerful Chernoff-type upper-tail estimates known for sampling with replacement automatically transfer to the case of sampling without replacement. For general weights, we use the same coupling to establish a sub-Gaussian concentration inequality. We also construct another martingale coupling which allows us to answer a question raised by Luh and Pippenger (2014) on sampling in Polya urns with different replacement numbers.