# Probability of having a majority element

I have $n$ random elements from 0 to $k$. What is the probability that there is some element which appears more than $n/2$ times (or $n/2$ times).

-

This is related to the problem of finding the integral of a normal distribution, in short this means that there is no simple formula that can solve your problem, you will have to do it as a sum of probabilities for a number of simpler cases.

The probability of a specific element appearing exactly $m$ times in a group of $n$ elements chosen randomly from a range of $k$ elements is: $$f(m, n, k) = \frac{(1/k)^m\ ((k-1)/k)^{n-m}\ n!}{m!\ (n-m)!}$$

So the probability of a specific element appearing $m$ or more times is: $$\sum_{p=roundup(n/2)}^n f(p, n, k)$$

For the case of any element appearing $m$ or more times things get tricky, I can't think of any simple way of taking the correlation between the numbers of different elements into account, but for your specific question less will do. You can simply multiply the result of the previous formula by $k$, but for even values of $n$ you will have to account for the special case where half of the elements is one value and half is another, since that will have been counted twice, so you will have to subtract that probability: $$\frac{k\ (k-1)\ (1/k)^n\ n!}{2\ (n/2)!^2}$$

Note that my $k$ is different from your $k$, since there are $k+1$ numbers from $0$ to $k$ you will have to add 1 to your $k$ before using it in the formulas.

-

If we interpret the $n$ random elements from $0$ to $k$ to mean that each different selection is equally likely, then this question does have a very nice closed form answer: see (1) below.

To be clear, say we are selecting two objects from the set $\lbrace 0,1 \rbrace$ then by each selection being equally likely we mean $\lbrace 00 \rbrace,$ $\lbrace 01 \rbrace$ and $\lbrace 11 \rbrace$ each have probability $1/3.$

So in the case where $k=1$ and $n=2,$ the probability that some object appears $> \lceil n/2 \rceil$ i.e. $2$ times, is $2/3.$ This is given by $(1)$ below.

Similarly, when $k=3$ and $n=3$ we're looking at the probability that some selection contains $3$ objects all the same. This can be seen to be $1/5$ by noting that if we select from $\lbrace 0,1,2,3 \rbrace$ then we have $4$ possibilities of the form $\lbrace 000 \rbrace$ (all the same), $12$ of type $\lbrace 001 \rbrace$ (two the same and one of another) and $4$ of type $\lbrace 012 \rbrace$ (all different). As a check, $(1)$ gives the probability as $1/5.$

So here's the derivation of $(1).$

The total number of ways we can place $n$ identical objects into $k+1$ boxes is ${n+k \choose k}.$

So now we need to find the number of ways of placing the $n$ identical objects into the $k+1$ boxes where one box contains $> \lceil n/2 \rceil$ objects.

Suppose there are $\lceil n/2 \rceil + i$ objects in one box, $1 \le i \le \lfloor n/2 \rfloor,$ then the other $\lfloor n/2 \rfloor - i$ objects can be distributed amongst the other $k$ boxes in $${ \lfloor n/2 \rfloor - i + k -1 \choose k – 1 }$$ ways.

Hence the total number of ways that one box can contain $> \lceil n/2 \rceil$ objects is $$(k+1) \sum_{i=1}^{ \lfloor n/2 \rfloor}{ \lfloor n/2 \rfloor - i + k -1 \choose k – 1 }$$ $$= \frac {k+1}{k} (\lfloor n/2 \rfloor + k -1){ \lfloor n/2 \rfloor + k - 2 \choose k – 1 }.$$

Hence the probability that one box contains $> \lceil n/2 \rceil$ objects is given by ( $k \ge 1, n \ge 1$ )

$$\frac {k+1}{k} \frac{ (\lfloor n/2 \rfloor + k -1){ \lfloor n/2 \rfloor + k - 2 \choose k – 1 } } { {n+k \choose k} }. \qquad (1)$$

-
It seems more likely to me that we should consider all the (k+1)^n selections as equally likely, so there are 4 choices of 2 items from {0,1}, not 3. – Ross Millikan Nov 18 '10 at 16:09
Yes, that's probably the interpretation of the poster, but my point is that with this interpretation there is a nice closed form answer. I thought this was interesting enough to point out. – Derek Jennings Nov 18 '10 at 16:13
I realy didn't understand: "To be clear, say we are selecting two objects from the set {0,1} then by each selection being equally likely we mean {00}, {01} and {11} each have probability 1/3." No! big mistake. each selection is equally likely between {00}, {01}, {10} and {11}. and each has probability 1/4 – Diego Nov 19 '10 at 15:46