Probability of correctly guessing the maximum event probability of a multinomial distribution

Question

I have a sample from multinomial distribution with $n$ trials, and $k=3$ options. I know that one of the event probabilities $p_i$ is larger than the two others (who are equal). I'm trying to guess which event has the biggest probability.

Clearly, the best strategy is to count the number of events of each type, and guess that the one with the biggest number of trials has has the biggest probability. For example, if $n=1000$ and I get $350$ times event $1$, $330$ times event $2$, and $320$ times event $3$, I'm going to guess that $p_1$ is larger than $p_2$ and $p_3$.

What is the probability of this strategy being correct? Is there a nice, easy-to-compute formula for it or a good approximation?

Answer 1

Suppose that the larger probability (corresponding to option 1) is $p$, and the other two are $q$ with $q<p$, $p+2q=1$. Let $(X,Y,Z)$ be the observations after $n$ trials. Your guess will be correct, if $X\ge Y$ and $X\ge Z$, so you need to compute \begin{align} \mathbb{P}(X\ge Y,X\ge Z)&=\sum_{i+j+k=n,\ i\ge \max(j,k)} \binom{n}{i,j,k}p^i(1-2p)^{j+k} \\ & =(1-2p)^n\sum_{i+j+k=n,\ i\ge \max(j,k)} \frac{n!}{i!j!k!}\left(\frac{p}{1-2p}\right)^i \\ & =(1-2p)^n\sum_{i=n/3}^n \frac{n!}{i!} \left(\frac{p}{2-4p}\right)^i \frac{2^{n-i}}{(n-i)!} B_{i,n}\\ &=(2-4p)^n\sum_{i=n/3}^n \binom{n}{i} \left(\frac{p}{2-4p}\right)^i B_{i,n} \end{align} where $$ B_{i,n}=\sum_{j+k=n-i,\ i\ge \max(j,k)} \binom{n-i}{j}\frac1{2^j}\frac1{2^{(n-i)-j}}. $$ Note that when $i\ge n/2$, then $B_{i,n}=1$ by the binomial theorem.

When $n/3\le i< n/2$ $$ B_{i,n}=\mathbb P(n-2i<Z<i)=\mathbb P\left(\left|Z-\frac{n-i}2\right|\right)\le \frac{3i-n}2 \approx \mathbb P\left(|\xi|\le \frac{6(i-n/3)}{\sqrt{n-i}}\right) $$ where $Z\sim Bin(n-i,1/2)$ and $\xi\sim N(0,1)$.

This combination gives you a way to compute the probability that your guess is correct.

A trivial inequality $B\le 1$ gives $$ \mathbb P(X\ge Y,X\ge Z)\le (2-4p)^n\sum_{i=0}^n \binom{n}{i} \left(\frac{p}{2-4p}\right)^i =(2-4p)^n\times \left(\frac{p}{2-4p}+1\right)^n =(2-3p)^n $$ which converges to zero exponentially fast if $p>1/3$.