# How often is data corrupted given how often a 3-way vote passes incorrect data?

Assume we have a noisy system where data is available via sample() and in order to filter out the noise someone has implemented the following voting algorithm:

sample_a = sample();
sample_b = sample();
if (sample_a != sample_b) {
sample_c = sample();
if (sample_a == sample_c)
return sample_a;
else if (sample_b == sample_c)
return sample_b;
}
return sample_a;


So it's almost a voting algorithm where we select the result appearing at least 2 out of 3 times. In the case where the first two match there is no third sample, but since the samples are not selected from a set but by adding a new "trial" I don't know if it matters that the third test is sometimes omitted.

My question is: If I have an estimate of how often the result of the above algorithm still yields an incorrect sample (based on outside knowledge of what makes a valid sample) can I reason back from that to the failure rate of the base sample() function?

My thinking: Take $P$ = probability of a bad sample. Consider the 8 combinations of right/wrong results in a 3-way vote: half of those cases have at least 2 failures. The 3 with two failures each have $P^{2}(1-P)$ chance of being wrong (two wrongs, one right) and the all-wrong case is $P^{3}$. The probability of the vote being wrong is then $3P^{2}(1-P)+P^{3}$ which simplifies to $-2P^{3}+3P^{2}$ which at least goes to the right limits (0 for $P\rightarrow 0$ and 1 for $P\rightarrow 1$). Leaning on Wolfram Alpha to solve that for me I get:

(I'm sure my tag selection is poor -- If I knew the right tags I would probably know the answer!)

• The fact that a third trial wouldn't occur if the '2 out of 3' was already decided is important. For example, wouldn't the 'all wrong' case just be $P^2$ since you wouldn't observe a third trial? Also, I don't think you're correctly counting the ways it could happen. For example, the $P^{2} (1-P)$ could happen as a fail-success-fail or success-fail-fail, so there are only two ways that could happen (since fail-fail-success would just be fail-fail, end). Jul 18, 2011 at 20:06
• @Macro If all samples are independent, then the value of the third sample is irrelevant in the case the first two agree. Therefore the distribution of the results truly is Binomial, as @Ben supposes, and the calculations should be carried out as if the third sample were always available. (Pascal and Fermat discussed exactly this question in the summer of 1654.)
– whuber
Jul 18, 2011 at 21:01

Everything you say is reasonable. Your binomial method works as whuber has said. Alternatively, you could add the probability of the first two being wrong, the first being wrong the second right and the third wrong, and the first right and the second and third wrong to get the same result: $P^2 + P(1-P)P + (1-P)P^2 = 3P^2-2P^3$.
I personally would not try to solve a cubic equation that way using complex numbers. If you have a particular value of $X$, you could find $P$ through numerical methods, or using a look-table, or very approximately using a graph like the following.
• I found plotting the function quite interesting, since at the macro scale it is approximately linear, offering no improvement of the base error rate. Only when $P$ is quite small does the voting actually start to really help. Jul 19, 2011 at 3:48