What is the best approximation for majority vote? The majority vote operation comes up fairly often in fault-tolerance (and no doubt other places), where the function outputs a bit equal to which ever value appears most frequently in the value of the input bits. For simplicity, let's assume that whenever the input contains an equal number of bits in state 0 and state 1, it outputs 0.

This can be generalized to dits where there are more than 2 possibilities for each input by returning the value which occurs most frequently in the input, and in the case of a tie, returning the most frequent value which comes first lexicographically. Let's call this function "plurality vote".

I am interested in the output of such a function when each input has a fixed probability distribution (and the distribution is the same for each dit in the input). Specifically I care about the following question.


  Given a set $S=\{S_1, S_2,... ,S_n\}$, if the set is independently
  randomly sampled $N$ times, with probability $p_i$ of choosing the
  $i^{th}$ element of $S$ each time, for a fixed choice of $v$ what
  is the probability that the plurality vote of these outputs $S_v$?


Now, it is straight forward to calculate the exact answer to the above question as a sum over multinomial distributions. However, for my purposes, this is less than ideal, and a closed for approximation would be better. So my question is:


  What closed form approximation to the above probability has the
  tightest bound on the maximum distance from the exact value?
If $p_v &gt; p_i$ for all $i \ne v$, then

$$
\mathrm{Pr}[\mbox{outcome is different from $v$}] \leq \min_T \left(Pr[B(N, p_v) \leq T] + Pr[\forall i \ne v \quad B(N, p_i) \geq T]\right),
$$

where $B(n, p)$ is binomial distribution, and $T$ is an arbitrary threshold. Plugging $T = N (p_v + \max_{i \ne v} p_v) / 2$ and using Chernoff bounds, one can upper-bound this probability as $e^{-\Omega(N)}$.

Of course, if $p_v$ is not maximum, then you get the opposite picture. With overwhelming probability $v$ is not outcome.