I examine a multinomial distribution with parameters $\vec{p} = [p_1, p_2, \ldots, p_s]$. I denote the cells by $C = \{ c_1, c_2, \ldots, c_s\}$. In this setting $p_{[i]}$ is the $i^{\text{th}}$ highest probability. That is $p_{[1]} \geq p_{[2]} \geq \ldots \geq p_{[s]}$. Of course, $\sum_{i = 1}^s p_i = \sum_{i = 1}^s p_{[i]} = 1$.
We have $r$ observations from this multinomial distribution and want to determine the cell $c_{[1]}$ (i.e., the cell that has the highest probability of appearing in some observation). To do that, we use the following simple rule: we select the cell with the highest number of observations (breaking ties arbitrarily). That is, if $\vec{N} = [N_1, N_2, \ldots, N_s]$ are the number of observations per cell for the $r$ total observations, then we select the cell $c_k$ for the $k$ that gives the maximum $N_k$.
The rule described gives the correct cell with probability:
$$ \Pi(r) = \sum_{l = 1}^s \frac{1}{l} \sum_{n = 1}^r \sum_{{\cal L}} \underset{\sum_{i \in \bar{{\cal L}}} k_i + l \cdot n = r}{\sum_{0 \leq k_i \leq n - 1, i \in \bar{{\cal L}}}} \left[\frac{r!}{(n!)^l \cdot \prod_{j \in \bar{{\cal L}}} k_j!} \cdot \prod_{z \in {\cal L}} p_z^n \cdot \prod_{w \in \bar{{\cal L}}} p_w^{k_w}\right] $$
where $l$ is the number of winners (cells with most number of ``votes''), $n$ is the number of votes for each winner, and ${\cal L}$ are subsets of $\{1, 2, \ldots, s\}$ including $[1]$ ($ = k$ maximizing $N_k$) with $|{\cal L}| = l$. Finally, $\bar{\cal L} = \{1, 2, \ldots, s\} - {\cal L}$.
Two questions:
- can $\Pi(r)$ be expressed in a simpler way?
- is there any work that describes how I prove that $\Pi(r)$ is non-decreasing on $r$?
