Singletons for Simpletons: Revisiting Windowed Backoff using Chernoff Bounds
share
For the well-known problem of balls dropped uniformly at random into bins, the number of singletons — those bins with a single ball — is important to the analysis of backoff algorithms. Existing arguments employ advanced tools to obtain concentration bounds. Here we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing several fundamental backoff algorithms.
READ FULL TEXT