Share
Explore BrainMass

# Binary message probability

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 &#8722; 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&#8722;1 is even, and 1 if x1+x2+· · ·+xn&#8722;1 is odd. When the message is received, the recipient checks whether yn has the same parity as y1+y2+· · ·+yn&#8722;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&#8722;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.

\$2.19