  Concentration inequalities quantify the deviation of a random variable from a
fixed value. In spite of numerous applications, such as opinion surveys or
ecological counting procedures, few concentration results are known for the
setting of sampling without replacement from a finite population. Until now,
the best general concentration inequality has been a Hoeffding inequality due
to Serfling [Ann. Statist. 2 (1974) 39-48]. In this paper, we first improve on
the fundamental result of Serfling [Ann. Statist. 2 (1974) 39-48], and further
extend it to obtain a Bernstein concentration bound for sampling without
replacement. We then derive an empirical version of our bound that does not
require the variance to be known to the user.
