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.

In coding theory when we encode 101 with 111000111 we have certain error probability. how can one prove that increasing the number of repetitions decreases the error probability.

Let the probability of flipping a bit on receiving is 1-p

If it done using three bits then

P[A] = If two bits are flipped. = 3C2 * p^2 * (1-p)

P[B] = If three bits are flipped = 3C3 * p^3

P[E] < P[A] + P[B]

Similarly one can calculate for n=4 but I am not able to generalize it.

share|improve this question
2  
+1: A surprisingly tricky question. Assume that the number of repetitions is odd, for otherwise it would not be clear how the receiver would resolve the ties. Trickiness comes from the fact that this is not true for $p=1/2$, but in that case no communication is taking place anyway. For $p>1/2$ the receiver needs to flip all the bits, but that is an anomalous case as well. Let's assume that $0<p<1/2$. –  Jyrki Lahtonen Aug 13 '11 at 8:14
1  
Generally p<1/2 is assumed in coding / information theory. –  zyx Aug 13 '11 at 8:41

4 Answers 4

up vote 3 down vote accepted

Well, it wasn't too tricky in the end. Let's write $S(p,k)$ for the probability of successfully transmitting a bit, when a repetition code of length $2k+1$ is used. As concluded by zyx (and myself) the question is interesting only, when $0<p<1/2$.

The claim is that for all $p$ in this range and all positive integers $k$ we have the inequality $$ S(p,k+1)>S(p,k). $$

To prove this assume that a repetition code of length $2k+3$ is used once. W.l.o.g. we can assume that a 0 was transmitted, so in the received bitstring of length $2k+3$ any bit is equal to $0$ with probability $1-p$ and equal to $1$ with the (cross-over) probability $p$. The transmission is successful, iff the majority of the bits are zeros. Let us look at the substring $s$ of the first $2k+1$ bits. A majority of those are 0s with probability $S(p,k)$.

In order to analyze the effect of the two additional bits we need to define two events: Call $s$ a nearly successful string (NS), if it has exactly $k$ 0s and consequently exactly $k+1$ 1s. IOW, the correct message lost by a single vote. Similarly call $s$ a nearly failed string (NF), if the correct message won by a single vote, i.e. there were exactly $k+1$ 0s and $k$ 1s in $s$.

When does the receiver seeing all the $2k+3$ bits make a correct decision about the transmitted bit? We see that his/her decision will be the same as it would be with the initial $2k+1$ bits of $s$ except in the two cases, where two last bits are both 1, and the string $s$ is nearly failed, and also in the case, where the two last bits are both 0, and the string $s$ was nearly successful. So we get the formula $$ S(p,k+1)=S(p,k)+(1-p)^2 P(NS)-p^2P(NF). $$ Here the binomial distribution tells us that $$ P(NS)={2k+1\choose k}p^{k+1}(1-p)^k,\qquad P(NF)={2k+1\choose k+1}p^k(1-p)^{k+1}. $$ Therefore (the two binomial coefficients are equal) $$ (1-p)^2P(NS)-p^2P(NF)={2k+1\choose k}p^{k+1}(1-p)^{k+1}(1-2p)>0. $$ Hence $S(p,k+1)>S(p,k)$ as claimed.

share|improve this answer

The probability of correctly encoding a bit by repeating it $2n+1$ times is $$ x_n=P(S_{n}\le n), $$ where the number of errors $S_{n}$ is binomial $(2n+1,p)$. Then the folowing holds.

If $0<p<\frac12$, the sequence $(x_n)$ is increasing.

To prove this, note that $S_{n+1}$ is distributed like $S_n+T$ where $T$ is binomial $(2,p)$ and independent on $S_n$. Furthermore, $T=0$, $1$ or $2$ hence $$ [S_{n+1}\le n+1]=[S_n\le n-1]\cup[S_n=n,T\le1]\cup[S_n=n+1,T=0]. $$ Since the events on the RHS are disjoint, this yields $$ x_{n+1}=x_n-P(S_n=n)+P(S_n=n)P(T\le1)+P(S_n=n+1)P(T=0), $$ that is, $$ x_{n+1}-x_n=P(S_n=n+1)P(T=0)-P(S_n=n)P(T=2). $$ Hence $x_{n+1}>x_n$ if and only if $P(S_n=n+1)P(T=0)>P(S_n=n)P(T=2)$.

But this last condition is easy to check. Assuming that $p\ne0$ and $p\ne1$, $$ \frac{P(S_n=n+1)}{P(S_n=n)}=\frac{p}{1-p}\qquad\text{and}\qquad \frac{P(T=2)}{P(T=0)}=\frac{p^2}{(1-p)^2}, $$ hence, assuming that $p\ne0$ and $p\ne1$, $x_{n+1}>x_n$ if and only if $p(1-p)^2>(1-p)p^2$ if and only if $1-p>p$ if and only if $p<\frac12$ and the desired result holds.

share|improve this answer
    
+1: You beat me to it by 3 minutes. –  Jyrki Lahtonen Aug 13 '11 at 9:36
    
Thanks! I understood the proof but I don't understand the notation that Sn is binomial (2n+1, p). please explain –  ghost-rider Aug 13 '11 at 18:55
    
The binomial distribution with parameters $(n,p)$ puts weight ${n\choose k}p^k(1-p)^{n-k}$ on $k$ for every integer $0\le k\le n$. –  Did Aug 13 '11 at 20:09

Let us consider only odd number of repetitions and $p < q$ where $p$ is the probability of a bit flip and $q=1-p$. Let $E_n$ be the event of an error when repeating a bit $2n+1$ times. Let us evaluate $P(E_{n+1})$. Here, error happens if there are more than $(n+1)$ flips. To find $P(E_{n+1}$), consider what happens in the first $2n+1$ transmissions out of the total $(2n+3)$ transmissions. There are 4 possibilities for the number of flips in the first $(2n+1)$ transmissions: (a) $\leq n-1$ flips, (b) exactly $n$ flips, (c) exactly $n+1$ flips, (d) $\geq n+2$ flips. The probability of event $E_{n+1}$ in these 4 cases are $0, p^2, 1-q^2$ and $1$ respectively.

For convenience, define $\alpha_n = {2n+1 \choose n} (pq)^n$. Then

$P(E_{n+1}) = p^2 \alpha_n q + (1-q^2) \alpha_n p + \sum_{k=n+2}^{2n+1} {2n+1 \choose k} p^k q^{n-k}$

The summation is the expression for $P(E_n)$ with the first term missing, i.e.

$\sum_{k=n+2}^{2n+1} {2n+1 \choose k} p^k q^{n-k} = P(E_n) - \alpha_n p$. Putting these together gives us

$P(E_{n+1}) - P(E_n) = \alpha_n pq (p-q) = {2n+1 \choose n} (pq)^{n+1}(p-q) < 0$.

Edit: Other answers beat me to it but I will leave this up anyway.

share|improve this answer

When one bit is transmitted as $n$ bits, so that whichever of 0 or 1 is more common in the received signal is treated as the correct value, the probability of this protocol being fooled by errors decreases exponentially (as a function of $n$).

If $f(p,n)$ is the probability of a failure, certainly $f$ decreases when $n$ is increased by $2$, but it is not true that $f(p,2k-1) > f(p,2k)$, because there is an additional failure mode for even $n$, with an equal number of 0's and 1's. One can randomly break the ties and in that version of the protocol the failure probabilities for $n=2k-1$ and $n=2k$ are equal.

share|improve this answer

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.