# Probability of detecting small bias in a die in the low confidence regime

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.

• (i) "The question can also be reduced to the following question about a regular unbiased die [...]." Can you give details on this? (ii) "What is the probability that the first count is exactly equal to the maximum of the rest of the counts?" I guess here you want some kind of asymptotics for this probability, right? Can you specify what kind would suffice for your purposes? – Iosif Pinelis Mar 7 at 12:18
• Anything of the form $\frac{1}{m} + \Omega(\sqrt{t}\gamma)$ would suffice. Here is the outline of the reduction: counts of the biased die R.V. can be represented as a mixture of Z_i. Each Z_i is the count of unbiased with i added to the count of the biased side. Without the adding i to the count the probability that any specific side has the largest count is $1/m$. So it suffices to analyze the marginal increase in prob. that the addition of $i$ to the count gives. This probability is essentially determined by the probability that the count is equal to the maximum of all the other counts. – Vitaly Mar 7 at 20:28