Alice wants to send Bob the result X of a fair coin flip over a binary symmetric channel that flips each bit with probability 0 < p < 1/2. To avoid errors in transmission, she encodes heads as a sequence of 2k+1 zeroes and tails as a sequence of 2k +1 ones.

(a) For any fixed k, give an upper bound on the probability of error of decoding.

(b) Show that for any fixed k, the above decoding scheme (of choosing the majority) minimizes the probability of error of decoding