Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A telephone company uses a best-of-five encoder. In this system every bit is transmitted 5 times and at the receiver a majority vote decides the value of each bit. If the probability of an uncoded bit error is 10^-3 (0.003), what is the probability of a decoded bit error?

My estimate is, please correct me if im wrong, that it should be: Pe:probability of an uncoded bit to be transmitted with an error Pc=(1-Pe):probability of correct transmision of an uncoded bit Pc*Pc*Pe*Pe*Pe=> (1-0.003)*(1-0.003)*0.003*0.003*0.003 Thanks in advance

share|improve this question
1  
Is it 10^-3 or 0.003? These are different numbers. –  Superbest Dec 31 '13 at 13:28
add comment

2 Answers 2

up vote 2 down vote accepted

Let p be the error probability for each, then the information is transmitted wrong if 3 or more bit is transmitted wrong.

so, it should be $10\times p^3(1-p)^2 + 5\times p^4(1-p) +p^5$

So: there are two things wrong with your calcuation:

(i) you did not count the number of different ways you can get 3 wrong and 1 correct. It could be

WWWCC WWCWC ... (w stand for wrong, c for correct)

(ii) you were not aware that making more than 3 errors also get your message wrong.

Notice that 10 and 5 comes from Binomial coefficients. They are respectively the number of ways to choose 3 objects from 5 and the number of ways getting 4 objects from 5. see http://en.wikipedia.org/wiki/Binomial_coefficient The cheapest way of getting these is via Pascal triangle (for simple problems like yours anyway)

What you are really asking is:

Let $X$ follow a binomial distribution with parameters $(5,p)$. What is $P(X\geq 3)$? http://en.wikipedia.org/wiki/Binomial_distribution might also be useful to you.

share|improve this answer
    
Thank you very much! You are absolutely right. –  Pokopik Jan 2 at 8:24
add comment

Since we have 5 bits, corruption will only occur if at least 3 bits are incorrect for the same block.

I will call an incorrectly transmitted bit a "success" since that's what we are watching out for.

Using the binomial distribution

The binomial distribution gives the probability of exactly $m$ successes in $n$ trials where the probability of each individual trial succeeding is $p$. With this method, you want the following:

  • Binomial at $(m=3, n=5, p=10^{-3})$ for probability of corruption due to exactly 3 fails
  • Binomial at $(m=4, n=5, p=10^{-3})$ for probability of corruption due to exactly 4 fails
  • Binomial at $(m=5, n=5, p=10^{-3})$ for probability of corruption due to exactly 5 fails

And you can sum these up to get the answer. Since summing values of the PDF like this is a very common operation, we have the CDF, which gives probability of $n$ or less successes. You want $n$ or more successes, so just do $1-Probability(n-1 \, or \, less \, successes)$. Here's a handy binomial calculator: http://stattrek.com/online-calculator/binomial.aspx

Without using the binomial distribution

You can also derive the expression yourself. Once again, you need:

  • Probability of getting $3$ successes
  • Probability of getting $4$ successes
  • Probability of getting $5$ successes

The probability of getting $m$ successes in a row is $p\cdot p\cdot p ... = p^m$ and the probability of getting $n-m$ non-successes in a row is likewise $(1-p)^{n-m}$. But for corruption, they don't have to be in a row, they can be rearranged. So, if you are calculating for $n=3$, there are several ways of picking the 3 bits out of 5 which will be wrong. This is done with the combination function, also called "n choose k", written as ${n \choose k} = \frac{5!}{(5-3)!3!}$ which gives you the number of ways that $k$ things can be chosen out of $n$ things.

So for $3$ successes, there are ${5 \choose 3}$ arrangements of incorrect bits possible, and each one has probability $p^3\cdot (1-p)^{5-3}$. You multiply the two to get the probability of getting $3$ successes in any arrangement.

Then you repeat for $4$ and $5$ and sum them up.

If you pay a bit of attention here, you will see that you have just derived the expressions for the PDF and CDF of the binomial distribution.

share|improve this answer
    
Thank you very much. You are both correct. The different ways of getting the same result eluded me. –  Pokopik Jan 2 at 8:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.