0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (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? $\endgroup$ – Iosif Pinelis Mar 7 at 12:18
  • $\begingroup$ 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. $\endgroup$ – Vitaly Mar 7 at 20:28

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.