1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't see why you expect such strong concentration to begin with. Even if $B_1, \dots, B_n$ were independent, the number of balls in the "bad" range would converge to a Poisson with mean $1$ as $n \to \infty$ (assuming that the range also shifts as we alter $n$ to preserve the $\frac1m$ probability). So we'd expect $2$ or more bins in the bad range with probability $1 - \frac2e$ in the limit. $\endgroup$ – Misha Lavrov Sep 7 '18 at 20:00
  • $\begingroup$ It seems that to obtain a concentration bound we need the "bad" range itself to be a function of the number of balls $n$. At a higher level, I am trying to define a "bad" range (which can depend on $n$ and $m$) such that with high probability, at most one bin will have a number of balls in that "bad" range. Having such a "bad" range will allow us to identify a bias in the assignment process so that if more than one bin is outside the range, we can conclude the balls are probably not being assigned uniformly at random. $\endgroup$ – jII Sep 7 '18 at 20:21
  • $\begingroup$ Are you attached to the idea of the bad range consisting of two intervals $[0,a] \cup [b, n]$? It seems easier to deal with a single interval $[a,n]$ being bad, especially since for $n$ not too much larger than $m$, we expect multiple bins with $0$ balls. $\endgroup$ – Misha Lavrov Sep 7 '18 at 22:02
  • $\begingroup$ @MishaLavrov I thought more about this, and it should be fine for the interval to be of the form $[a,n]$. Effectively, finding such a range and concentration will bound will tell us that, if the assignment process is non-uniform, then with high probability some bin will have a number of balls whose probability is vanishingly small under a $\mathrm{Binomial}(n, 1/m)$ distribution. $\endgroup$ – jII Sep 8 '18 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.