1. A binary message is sent over a noisy channel. The message is a sequence
x1, x2, . . . , xn of n bits (xi 2 {0, 1}). Since the channel is noisy, there is a chance that any bit might be corrupted, resulting in an error (a 0 becomes a 1 or vice versa).
Assume that the error events are independent. Let p be the probability that an
individual bit has an error (0 < p < 1/2). Let y1, y2, . . . , yn be the received message (so yi = xi if there is no error in that bit, but yi = 1 − xi if there is an error there).
To help detect errors, the nth bit is reserved for a parity check: xn is defined to be
0 if x1+x2+· · ·+xn−1 is even, and 1 if x1+x2+· · ·+xn−1 is odd. When the message is received, the recipient checks whether yn has the same parity as y1+y2+· · ·+yn−1.
If the parity is wrong, the recipient knows that at least one error occurred; otherwise, the recipient assumes that there were no errors.
(a) For n = 5, p = 0.1, what is the probability that the received message has errors which go undetected?
(b) For general n and p, write down an expression (as a sum) for the probability that the received message has errors which go undetected.
(c) Give a simplified expression, not involving a sum of a large number of terms, for the probability that the received message has errors which go undetected.
2. A coin with probability p of heads is flipped n times independently. Let Xi be 1
if the ith flip is heads and 0 otherwise, and let Z be the number of heads. Show that
for any two sequences a1, . . . , an and b1, . . . , bn each consisting of k 1's and n−k 0's, P(X1 = a1, . . . ,Xn = an|Z = k) = P(X1 = b1, . . . ,Xn = bn|Z = k).