Concentration inequalities for the sum in sampling without replacement: an approach via majorization

Abstract

Let $P=(x_1,\dots ,x_n)$ be a population consisting of $n\ge 2$ real numbers whose sum is zero, and let $k<n$ be a positive integer. We sample $k$ elements from $P$ without replacement and denote by $X_P$ the sum of the elements in our sample. In this article, using ideas from the theory of majorization, we deduce non-asymptotic lower and upper bounds on the probability that $X_P$ exceeds its expected value.

15 pages