Imagine we have an algorithm for solving some decision problem. Suppose that the algorithm makes a decision at random and returns the correct answer with probability 1/2 + 6, for some o > 0, so just a bit better than a random guess. To improve the performance, we run the algorithm /V times and take the majority vote. Show that, for any & E (0, 1), the answer is correct with probability 1 -s, as long as N 2 In (4) 252 Hint: Use the following theorem. Theorem (Hoeffding's inequality for general bounded random variables). Let X1, ..., XN be independent random variables. Assume that X; e [m;, Mi] for every i. Then, for any t >0, we have N 2+2 PE(X, - EX;) 2t exp i=1 EM(Mi - m;)