Suppose two algorithms perform equally well on easy instances; their performance on the hard ones is as good as agreement-by-coin-flipping would allow.
the difference in the number of "correct" answers on hard instances for algorithms A and B is a random variable S satisfying S = R i=1 X i where X 1 , .