Repeating a message
A (very) noisy channel is known to flip bits 20% of the time. Alice decides to send the same bit multiple times, and Bob will interpret the message as the bit he receives more times (e.g. if Bob received 0, 1, 1, he would conclude the message was 1).
If Alice wants to ensure the message is correctly received with probability at least 95%, what is the minimum number of times Alice needs to send each bit?
The answer is 7.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Relevant wiki: Error correcting codes
The probability for k successes in n trials, each independent and of probability p, is given by the binomial distribution. P r ( X = k ) = ( k n ) p k ( 1 − p ) n − k In this case I think it's easiest to interpret 'k successes' as the number of bits flipped in a bit sequence of length n, and each bit flip has a probability of 0.2. But because this tells the probability of an incorrect message being received then to answer the question we need to look for a total probability of less than 5%. Furthermore, an incorrect message will be received any time the number of bits flipped is greater than or equal** to the number of total bits, so we need to add together several binomial probabilities.
Let's try a bit length n = 3 first. An incorrect transmission will be received if two or three bits are flipped so P r ( f a i l u r e ) = P r ( X = 2 ) + P r ( X = 3 ) = ( 2 3 ) 0 . 2 3 ( 1 − 0 . 2 ) + 0 . 2 3 = . 1 0 4 This is above 5% so 3 bits is not good enough. Repeat with more bits and you will find that the n=7 the smallest that works, where 4, 5, or 6 bits must be flipped for Bob to receive the incorrect message.
** I say "or equal to" because if Bob received a 50/50 result with an even number of bits he can not be expected to interpret it correctly.