2011/07/07 by Kyle Luh, Luh, Kyle J., Pippenger, Nicholas +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Census and Population Estimation #Data Management and Algorithms #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1107.1533
openalex publication_date 2011/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hoeffding has shown that tail bounds on the distribution for sampling from a\nfinite population with replacement also apply to the corresponding cases of\nsampling without replacement. (A special case of this result is that binomial\ntail bounds apply to the corresponding hypergeometric tails.) We give a new\nproof of Hoeffding's result by constructing a martingale coupling between the\nsampling distributions. This construction is given by an explicit combinatorial\nprocedure involving balls and urns. We then apply this construction to create\nmartingale couplings between other pairs of sampling distributions, both\nwithout replacement and with "surreplacement" (that is, sampling in which not\nonly is the sampled individual replaced, but some number of "copies" of that\nindividual are added to the population).\n