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.

  • $\begingroup$ For $m=2$, we have exact lower bounds, for all regimes: e-publications.org/ims/submission/AOS/user/submissionFile/… The calculations were indeed painful. $\endgroup$
    – Aryeh
    Commented Mar 7, 2019 at 8:11
  • $\begingroup$ 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. $\endgroup$
    – Vitaly
    Commented Mar 7, 2019 at 20:08
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Commented Mar 7, 2019 at 20:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – Clement C.
    Commented Mar 7, 2019 at 22:38
  • $\begingroup$ 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! $\endgroup$
    – Vitaly
    Commented Mar 8, 2019 at 4:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.