SIMPLE PROOFS OF OCCUPANCY TAIL BOUNDS

We give a simple proof of an occupancy tail bound in the balls and bin s experiment using the method of bounded differences in expected form. We also indicate how a short, calculation-free proof of another occup ancy tail bound follows from an extension of the standard Chernoff-Hoe ffding bounds to variables that satisfy some general notions of negati ve dependence. (C) 1997 John Wiley & Sons, Inc.