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:

  1. can $\\Pi(r)$ be expressed in a simpler way?
  2. is there any work that describes how I prove that $\\Pi(r)$ is non-decreasing on $r$?
  • $\begingroup$ The case where $s=2$ and $r$ is odd is known as Condorcet's Jury Theorem (1785), a fundamental result in theoretical political science. There has been some work since then. $\endgroup$ – Douglas Zare Sep 21 '11 at 8:26
  • $\begingroup$ Thanks for the answer Douglas. Do you (or anyone else) happen to know if something like what I am asking is already proven, if it is an open problem, or if there is a belief that it is true? $\endgroup$ – Patrick V Sep 21 '11 at 21:08
  • $\begingroup$ I haven't worked out the details but it seems to me that the second question would be easier with a random number of votes with a Poisson distribution, i.e., let the voters appear via a Poisson process. $\endgroup$ – Douglas Zare Sep 26 '11 at 16:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.