Probability of Error going unnoticed in a noisy channel

Question

I had a doubt regarding a selected question in the book Introduction to Probability by Joseph K. Blitzstein and Jessica Hwang. I seem to have missed out a key point in my approach to the problem. The question is the following

A message is sent over a noisy channel. The message is a sequence x₁, x₂, . . . , x_n of n bits where x_i belongs to the set {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 y₁, y₂, . . . , y_n be the received message (so y_i = x_i if there is no error in that bit, but y_i = 1− x_i if there is an error there).

To help detect errors, the nth bit is reserved for a parity check: x_n is defined to be 0 if x₁ + x₂ + · · · + x_n−1 is even, and 1 if x₁ + x₂ + · · · + x_n−1 is odd. When the message is received, the recipient checks whether y_n has the same parity as y₁ +y₂ +· · ·+y_n−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?

Solution

My approach is the following

Scenario 1

Let x₅ be 1 which means that x₁+...+x₄ is odd. For the error to be undetected, the allowed number of bit changes should be 2. So,

$P$(error not detected|x₅=1)=$$\binom {4}{2} 0.1^{2}0.9^{2}$$

Scenario 2

Let x₅ be 0 which means that x₁+...+x₄ is even. For the error to be undetected, the allowed number of bit changes should be 2 as well. So,

$P$(error not detected|x₅=0)=$$\binom {4}{2} 0.1^{2}0.9^{2}$$

So by using the Law of Total Probability

$P$(error not detected) = $P$(x₅=1) * $P$(error not detected|x₅=1) + $P$(x₅=0) * $P$(error not detected|x₅=0) = $$\binom {4}{2} 0.1^{2}0.9^{2}$$ where $P$(x₅=1) = $P$(x₅=0) = 0.5

But looking at the solution manual, the answer is

$$\binom {5}{2} 0.1^{2}0.9^{3} + \binom {5}{4} 0.1^{4}0.9^{1}$$

My assumption is that x₅ is fixed based on the sum of the previous bits. But the solution takes into account the 5th bit as well. I am not able to figure out the mistake in my approach. It would be of great help if someone could help me figure this out. Thank You in advance!

Answer 1

The fifth bit is sent over the channel too, so there is a possibility of it being corrupted as well. If there are an odd number of errors, the checksum will fail and the message will be marked as an error. If there are an even number of errors, the checksum will succeed and the message will go through.

In the case where there are two or four errors, the message will have an error in it, but will be accepted anyway. So the probability of there being errors but it going undetected is just the probability of there being two or four errors out of five, which is what they calculate.

A single error in the fifth bit would result in a 'false positive' where the message portion is correct but the message is discarded anyway, I suppose, but that's not the same thing as an error that goes undetected.

Answer 2

An odd number of bit corruptions will make it look like there was "at least one error" and in that case there must have been, since 0 is not an odd number.

Therefore it is the even number of corruptions you need to consider.

Hint : What are the probabilities of two errors and four errors?