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.
On
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.
On
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.
On
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.
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.