Mixing
Probability of Error going unnoticed in a noisy channel
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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 x1, x2, . . . , xn of
n bits where xi 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 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?
Solution
My approach is the following
Scenario 1
Let
x5 be 1 which means that x1+...+x4 is odd.
For the error to be undetected, the allowed number of bit changes should be 2. So,
$P$(error not detected|x5=1)=$$binom 42 0.1^20.9^2$$
Scenario 2
Let
x5 be 0 which means that x1+...+x4 is even.
For the error to be undetected, the allowed number of bit changes should be 2 as well. So,
$P$(error not detected|x5=0)=$$binom 42 0.1^20.9^2$$
So by using the Law of Total Probability
$P$(error not detected) = $P$(x5=1) * $P$(error not detected|x5=1) + $P$(x5=0) * $P$(error not detected|x5=0) = $$binom 42 0.1^20.9^2$$
where $P$(x5=1) = $P$(x5=0) = 0.5
But looking at the solution manual, the answer is
$$binom 52 0.1^20.9^3 +
binom 54 0.1^40.9^1$$
My assumption is that x5 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!
statistics binomial-distribution
asked Sep 1 at 6:46
adhok
305
add a comment |Â
up vote
1
down vote
favorite
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 x1, x2, . . . , xn of
n bits where xi 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 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?
Solution
My approach is the following
Scenario 1
Let
x5 be 1 which means that x1+...+x4 is odd.
For the error to be undetected, the allowed number of bit changes should be 2. So,
$P$(error not detected|x5=1)=$$binom 42 0.1^20.9^2$$
Scenario 2
Let
x5 be 0 which means that x1+...+x4 is even.
For the error to be undetected, the allowed number of bit changes should be 2 as well. So,
$P$(error not detected|x5=0)=$$binom 42 0.1^20.9^2$$
So by using the Law of Total Probability
$P$(error not detected) = $P$(x5=1) * $P$(error not detected|x5=1) + $P$(x5=0) * $P$(error not detected|x5=0) = $$binom 42 0.1^20.9^2$$
where $P$(x5=1) = $P$(x5=0) = 0.5
But looking at the solution manual, the answer is
$$binom 52 0.1^20.9^3 +
binom 54 0.1^40.9^1$$
My assumption is that x5 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!
statistics binomial-distribution
asked Sep 1 at 6:46
adhok
305
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 x1, x2, . . . , xn of
n bits where xi 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 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?
Solution
My approach is the following
Scenario 1
Let
x5 be 1 which means that x1+...+x4 is odd.
For the error to be undetected, the allowed number of bit changes should be 2. So,
$P$(error not detected|x5=1)=$$binom 42 0.1^20.9^2$$
Scenario 2
Let
x5 be 0 which means that x1+...+x4 is even.
For the error to be undetected, the allowed number of bit changes should be 2 as well. So,
$P$(error not detected|x5=0)=$$binom 42 0.1^20.9^2$$
So by using the Law of Total Probability
$P$(error not detected) = $P$(x5=1) * $P$(error not detected|x5=1) + $P$(x5=0) * $P$(error not detected|x5=0) = $$binom 42 0.1^20.9^2$$
where $P$(x5=1) = $P$(x5=0) = 0.5
But looking at the solution manual, the answer is
$$binom 52 0.1^20.9^3 +
binom 54 0.1^40.9^1$$
My assumption is that x5 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!
statistics binomial-distribution
asked Sep 1 at 6:46
adhok
305
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 x1, x2, . . . , xn of
n bits where xi 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 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?
Solution
My approach is the following
Scenario 1
Let
x5 be 1 which means that x1+...+x4 is odd.
For the error to be undetected, the allowed number of bit changes should be 2. So,
$P$(error not detected|x5=1)=$$binom 42 0.1^20.9^2$$
Scenario 2
Let
x5 be 0 which means that x1+...+x4 is even.
For the error to be undetected, the allowed number of bit changes should be 2 as well. So,
$P$(error not detected|x5=0)=$$binom 42 0.1^20.9^2$$
So by using the Law of Total Probability
$P$(error not detected) = $P$(x5=1) * $P$(error not detected|x5=1) + $P$(x5=0) * $P$(error not detected|x5=0) = $$binom 42 0.1^20.9^2$$
where $P$(x5=1) = $P$(x5=0) = 0.5
But looking at the solution manual, the answer is
$$binom 52 0.1^20.9^3 +
binom 54 0.1^40.9^1$$
My assumption is that x5 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!
statistics binomial-distribution
asked Sep 1 at 6:46
adhok
305
asked Sep 1 at 6:46
adhok
305
asked Sep 1 at 6:46
adhok
305
asked Sep 1 at 6:46
adhok
305
305
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
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.
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
add a comment |Â
up vote
1
down vote
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?
answered Sep 1 at 7:36
mathreadler
13.8k72058
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
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.
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
add a comment |Â
up vote
3
down vote
accepted
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.
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
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.
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
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.
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
edited Sep 1 at 7:33
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
answered Sep 1 at 7:16
spaceisdarkgreen
28.7k21548
28.7k21548
add a comment |Â
add a comment |Â
up vote
1
down vote
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?
answered Sep 1 at 7:36
mathreadler
13.8k72058
add a comment |Â
up vote
1
down vote
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?
answered Sep 1 at 7:36
mathreadler
13.8k72058
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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?
answered Sep 1 at 7:36
mathreadler
13.8k72058
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?
answered Sep 1 at 7:36
mathreadler
13.8k72058
answered Sep 1 at 7:36
mathreadler
13.8k72058
answered Sep 1 at 7:36
mathreadler
13.8k72058
answered Sep 1 at 7:36
mathreadler
13.8k72058
13.8k72058
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2901436%2fprobability-of-error-going-unnoticed-in-a-noisy-channel%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
