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

<p>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 <span class="math-container">$\gamma \leq \frac{1}{\sqrt{tm}}$</span> (which is roughly the standard deviation of each of the counts). You can also assume that <span class="math-container">$t\geq c m \log m$</span> (for any fixed constant <span class="math-container">$c$</span>).
In the case of <span class="math-container">$m=2$</span> a simple calculation shows that success probability in this regime is <span class="math-container">$\geq \frac{1}{2} + \Omega(\sqrt{t}\gamma)$</span>.
More generally, based on some back-of-the-envelope calculations and simulations the answer should be <span class="math-container">$\geq \frac{1}{m} + \Omega(\sqrt{t}\gamma)$</span>. However, I do not see a formal argument that proves this (and a direct calculation in this case seems very painful).</p>

<p>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?</p>

<p>Would be grateful for references or analysis suggestions. </p>

CC BY-SA 4.0
2019-03-07T08:11:09.613Z
For $m=2$, we have exact lower bounds, for all regimes:
https://www.e-publications.org/ims/submission/AOS/user/submissionFile/27215?confirm=930582eb
The calculations were indeed painful.
Aryeh
CC BY-SA 4.0
2019-03-07T20:08:49.397Z
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
CC BY-SA 4.0
2019-03-07T20:56:50.447Z
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
CC BY-SA 4.0
2019-03-07T22:38:16.260Z
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.
CC BY-SA 4.0
2019-03-08T04:46:34.650Z
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
CC BY-SA 4.0
2019-03-08T17:16:28.487Z
@Vitaly I hope this works out!
Clement C.
<pr.probability>
Probability of detecting small bias of a die in the low confidence regime / balls and bins
Vitaly
# Probability of detecting small bias of a die in the low confidence regime / balls and bins

(Asked by: username_0 on 2019-03-07)

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.

**Tags:** pr.probability

> **Comments:**
> **username_1**: For $m=2$, we have exact lower bounds, for all regimes: https://www.e-publications.org/ims/submission/AOS/user/submissionFile/27215?confirm=930582eb The calculations were indeed painful.  
> **username_0**: Thanks, username_1. 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.  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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!  
> **username_2**: @username_0 I hope this works out!  

---

## 0 answers

