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 Mar 7 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 Mar 7 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 Mar 7 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. Mar 7 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 Mar 8 at 4:46

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.