MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?
share|cite|improve this question
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. – Douglas Zare Sep 21 '11 at 8:26
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? – Patrick V Sep 21 '11 at 21:08
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. – Douglas Zare Sep 26 '11 at 16:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.