I have been thinking of the following problem. Suppose I throw $n$ balls into $m$ bins, each bin selected uniformly at random. Let $B _i$ $(i=1,2,\dots,m)$ denote the number of balls that land in bin $i$. Then we have that $B_i \sim \mathrm{Binom}(n, 1/m)$, with $\mathbb{E}[B_i] = n/m$.
Fix integers $a, b$ such that $0 \le a < b \le n$ and $$\Pr[B_i \le a \mbox{ or } b \le B_i] \approx 1/m.$$ In other words, the probability that bin $i$ has a number of balls in the "bad" range $\{0,\dots,a,b,\dots,n\}$ is $1/m$.
Let $E_i = \mathbb{I}[ B_i \le a \mbox{ or } b \le B_i]$ be the indicator for the event that bin $i$ is in the "bad" range. Then
$$ \mathbb{E}\left[\sum_{i=1}^{m}E_i \right] = \sum_{i=1}^{m}\mathbb{E}\left[E_i \right] = m(1/m) = 1, $$
so the expected number of bins that have balls in the bad "range" is exactly 1. Is there a way to establish a sharp concentration bound around this expectation, so that the number of bins in the "bad" range is no more than 1 with high probability? (I am assuming that $m$ stays fixed as $n$ increases.)
The Chernoff bound does not seem applicable because the binomial random variables $B_i$ are dependent: $\sum_{i=1}^{m}B_i = n$ (w.p. 1). The Chebyshev bound (assuming the negative covariance is zero) is too loose.