  We develop a general technique for bounding the tail of the total variation
distance between the empirical and the true distributions over countable sets.
Our methods sharpen a deviation bound of Devroye (1983) for distributions over
finite sets, and also hold for the broader class of distributions with
countable support. We also provide some lower bounds of possible independent
interest.
