Skip to main content
Tweeted twitter.com/#!/StackStats/status/93071034021974016
edited tags
Link
whuber
  • 333.5k
  • 63
  • 792
  • 1.3k
Source Link
Ben Jackson
  • 271
  • 1
  • 3
  • 10

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:

solved for P

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