<p>If $p_v &gt; p_i$ for all $i \ne v$, then</p>

<p>$$
\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),
$$</p>

<p>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)}$.</p>

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

CC BY-SA 3.0
2011-11-03T07:26:41.813Z
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
CC BY-SA 3.0
2011-11-03T14:01:54.207Z
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
CC BY-SA 3.0
2011-12-03T14:07:35.990Z
@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
CC BY-SA 3.0
2011-11-02T22:01:49.400Z
2011-11-02T22:13:28.277Z
2011-11-02T22:13:28.277Z
ilyaraz
<p>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.</p>

<p>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".</p>

<p>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.</p>

<blockquote>
  <p>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$?</p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>What closed form approximation to the above probability has the
  tightest bound on the maximum distance from the exact value?</p>
</blockquote>

CC BY-SA 3.0
2011-11-02T16:37:43.377Z
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
CC BY-SA 3.0
2011-11-04T21:35:01.303Z
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
CC BY-SA 3.0
2011-11-04T21:42:56.410Z
@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
CC BY-SA 3.0
2012-01-02T23:44:14.587Z
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
<co.combinatorics>
What is the best approximation for majority vote?
Joe Fitzsimons
# What is the best approximation for majority vote?

(Asked by: username_0 on 2011-11-02)

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?

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-11-02. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  
> **username_5**: @username_4 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 :)  

---

