# Binary message probability

Please show answers with all steps.

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).

#### Solution Preview

Question 1(a)

P(received message has errors which go undetected)

= P(parity bit correct AND even number of errors in data) +

P(parity bit wrong AND odd number of errors in data)

= P(parity bit correct)·P(even number of errors in data) +

P(parity bit wrong )·P( odd number of errors in data)

= 0.9 × [P(2 errors) + P(4 errors)] +

0.1 × [P(1 error ) + P(3 errors)] +

= 0.9 × [4C2 × 0.1^2 × 0.9^2 + 4C4 × 0.1^4 × 0.9^0 ] +

0.1 × [4C1 × 0.1^1 × 0.9^3 + 4C3 × 0.1^3 × 0.9^1 ]

= 0.9 × [ 0.0486 + 0.0001 ] +

0.1 × [ 0.2916 + 0.0036 ]

= 0.07335

Question 1(b)

...

#### Solution Summary

This is a probability question regarding a binary message.