18

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?

Joe Fitzsimons
  • 13,675
  • 47
  • 91
  • I don't know, but I would suggest the search phrase, "control theory consensus" or "control theory consensus problem." It is a different problem from the distributed computing consensus problem, and may be what you need. – Aaron Sterling Nov 02 '11 at 16:37
  • Are you looking for an approximation which works well when N is large compared to n? If so, the tie-breaking rule must be irrelevant. – Tsuyoshi Ito Nov 04 '11 at 21:35
  • @TsuyoshiIto: Yes, I am, and indeed that rule is irrelevant, but I wanted to make sure the question was well posed. I don't really care about how ties are broken, since it is easy to bound that discrepency. – Joe Fitzsimons Nov 04 '11 at 21:42
  • 1
    Well, here is back of the envelope estimate... Let $Y_i$ be the number of times you pick the set $S_i$. This is a binomial variable. Pretend they are independent. Now, for a fixed value of $Y_v$, you can compute the probability of getting this value of $Y_v$, and for this value compute the probability it wins over all the other variables. This should give a pretty good bounds on the probability. They are of course not the tightest - the more dependency you are willing to take into account, the more precise your estimate is going to be, but the more computation you are going to have to do. – Sariel Har-Peled Jan 02 '12 at 23:44

1 Answers1

1

If $p_v > 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.

ilyaraz
  • 1,569
  • 18
  • 33
  • 1
    Thanks for thinking about the problem, but this isn't what I'm looking for. It isn't a closed form. I would need to sum over an unbounded number of exponentials. I already know how to write the exact solution and I know lots of approximations for individual terms, but that's not what I want. I'm looking for a closed form approximation to the solution, not to individual terms. I also need a decent bound on the error. – Joe Fitzsimons Nov 03 '11 at 07:26
  • 1
    You can get closed form using the same method (if you are happy with additional factor $n$). And to bound the error, you can use Berry-Eseen theorem instead of Chernoff bound. – ilyaraz Nov 03 '11 at 14:01
  • @ilyaraz I'm trying to understand your first disequation. Can u explaine me better why it holds? I think that you've used union bound in some way but I can't understand. Thanks :) – AntonioFa Dec 03 '11 at 14:07