# Probability and Bernoulli trials

The white noise model is often used when considering the problem of errors in a transmitted binary msg. This model is based on the following asssumptions:

a) there is an equal probability,p, of an error in each bit of the msg

b) errors in different bits of the msg are independent


One way of encoding a binary msg so as to make it error detecting is to count the number of 1s in the msg and then append an extra bit to it so that the resulting msg (including the additional bit) has even parity, that is , has an even number of 1s in it. If a msg is received with an odd number of 1s in it, the receiver then knows that the msg contains an odd number of errors. The receiver can't detect an even number of errors with this device.

 1) Determine the probability of an undetected error in a binary
msg comprising n bits( including the parity bit),
assuming the white noise models for errors in the msg.

2) Determine the probability of an undetected error in
a binary msg consisting of 8 bits(including the parity bit),
assuming the white noise model for errors with p =1/3 in the msg.

---------------------------------------------------


Proposed solution: From (b) above we are told that "errors in different bits of the msg are independent", therefore I believe that the problem can be solved using Bernoulli trials. We know that P = 0.5 (where P = the probability of success that a bit is error free) and Q = 0.5 (where Q = the probability of an error in a bit).

The probability of exactly k successes in n independent Bernoulli trials, with probability of success p and probability of failure q = 1 − p, is

$C(n, k)p^{k}q^{n−k}$.

In the case of trying to solve (1), would it be correct to assume we have $C{n \choose 2}$ potential combinations or is this wrong? I am unsure if the parity bit should be included in any analysis if that makes sense. Please could someone point me in the right direction if I have gone astray here

Many thanks

-
Hint: You are on the right path, but keep in mind that what you need to compute is the probability of an even number of errors, not just $2$ errors. That is, $2$ errors or $4$ errors or $6$ errors or $\ldots$ or $n$ errors (if $n$ is even); the last term is $n-1$ errors if $n$ is odd. The $n$ bits must include the parity bit also. – Dilip Sarwate Dec 5 '12 at 19:47
(2) is just a special case of (1), so solve (1) first and use that result to solve (2). I don't know where you got $p=0.5$, since (1) doesn't specify $p$ and (2) clearly says $p = 1/3 \neq 0.5$. – Jonathan Christensen Dec 5 '12 at 20:01
@JonathanChristensen +1..good point. I had misinterpreted (1) to mean p = .5 which is not the case as you point out – bosra Dec 5 '12 at 20:49
@DilipSarwate - thanks for the feedback. Ok so if we have four bits (including the parity bit) as follows: 0 1 0 1. The bits in index 1(which is 1) and index 2( which is zero) here could have errors. So the number of undetected errors in N bits could potentially be as high as n-2 otherwise we should catch an odd number of errors with the parity bit. Am I right in suggesting k = n-2? – bosra Dec 5 '12 at 21:22
You are completely missing the point. $4$ bits $(a_1,a_2,a_3.a_4)$ are transmitted including one parity bit $a_4$. The transmitter chooses $$a_4=a_1\oplu sa_2\oplus a_3 ~\Rightarrow a_1\oplus a_2\oplus a_3\oplus a_4=0.$$ The receiver gets $(b_1,b_2,b_3,b_4)$ where the events $(b_i\neq a_i)$ are independent and of probability $p$. The receiver computes $b_1\oplus b_2\oplus b_3\oplus b_4$. If the XOR sum is $0$, the receiver assumes that no errors have occurred. If the XOR sum is $1$, then the receiver says that error(s) have occurred. In fact, an odd number of the events $(b_i\neq a_i)$ – Dilip Sarwate Dec 6 '12 at 0:41