# Probability of detecting small bias of a die in the low confidence regime / balls and bins

We are given a biased $$m$$-sided die: one of the sides has probability $$\frac{1}{m} + \gamma$$ and all the rest have probability $$\frac{1}{m} - \frac{\gamma}{m-1}$$ each. The goal is to figure out which of the sides is biased given $$t$$ independent throws. Naturally, the optimal way to do that is to output the side with the largest count (with randomized tie breaking).

I'd like to give a lower bound on the success probability of this method when the number of throws is too small to get high probability of success. More formally, assume that $$\gamma \leq \frac{1}{\sqrt{tm}}$$ (which is roughly the standard deviation of each of the counts). You can also assume that $$t\geq c m \log m$$ (for any fixed constant $$c$$). In the case of $$m=2$$ a simple calculation shows that success probability in this regime is $$\geq \frac{1}{2} + \Omega(\sqrt{t}\gamma)$$. More generally, based on some back-of-the-envelope calculations and simulations the answer should be $$\geq \frac{1}{m} + \Omega(\sqrt{t}\gamma)$$. However, I do not see a formal argument that proves this (and a direct calculation in this case seems very painful).

The question can also be reduced to the following question about a regular unbiased die (or the standard balls-and-bins model). What is the probability that the first count is exactly equal to the maximum of the rest of the counts?

Would be grateful for references or analysis suggestions.

• For $m=2$, we have exact lower bounds, for all regimes: e-publications.org/ims/submission/AOS/user/submissionFile/… The calculations were indeed painful. – Aryeh Mar 7 '19 at 8:11
• Thanks, Aryeh. Which specific statement in your paper are you referring to? The exact constant in front of the $\sqrt{t}\gamma$ term is not particularly important for me so $m=2$ case is easy using the reduction I mentioned. – Vitaly Mar 7 '19 at 20:08
• I was referring to Theorem 2.4, and I'm wondering if similar techniques can be used to establish the $m>2$ case. The calculations are pretty hairy though. – Aryeh Mar 7 '19 at 20:56
• A possible approach, not quite sure where it would lead: instead of $t$ i.i.d. samples from your die, assume you take $\mathrm{Poisson}(t)$. Then the number of occurrences of each side are independent r.v.'s: the first is $\mathrm{Poisson}(\frac{t}{m}+\gamma t)$, the $m-1$ others are $\mathrm{Poisson}(\frac{t}{m}-\frac{\gamma t}{m-1})$. So in that setting (which I would gather is near equivalent to the non-Poissonized one), you need to analyze the maximum of $m-1$ i.i.d. Poisson r.v's. – Clement C. Mar 7 '19 at 22:38
• Poissonization seems like a good idea! (at least one of the approaches I considered got stuck because of the dependence). Dealing with Poisson density is also easier than with binomial approximation. I'll try to get it to work from here. Thanks Clement! – Vitaly Mar 8 '19 at 4:46