PROBLEM 5 (Corrupted Messages). Alice wants to send a message to Bob, where the message is a sequence of bits. Alice sends her message through a noisy communication channel that randomly ips the bits: a 0 bit is incorrectly transmitted as a 1 with probability %, and it is correctly transmitted with probability g; a 1 bit is incorrectly transmitted as a 0 with probability %, and it is correctly transmitted with probability %; each bit is ipped independently from the other bits. (a) Alice chooses a single bit uniformly at random and sends it to Bob. What is the probability that Bob receives it correctly? (b) What is the probability that Bob receives the message 10110011 correctly? (c) In an effort to improve the probability that Bob receives the correct message, Alice transmits each bit three times and Bob uses the majority rule to decode. More precisely, Alice transmits a 0 as 000 and a 1 as 111. Bob decodes the three bits received as a 0 if there are at least 2 Os, and as a 1 otherwise. What is the probability that after Alice transmits a 000, Bob correctly decodes what he receives to 0? (d) Alice again chooses a single bit uniformly at random and now she uses the scheme in part (c) to send it. What is the probability that the bit was 0 given that Bob received the sequence 101