Repetition code and binary symmetric channel, where error is near 1/2

I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error probability is close to 1/2, so the capacity of the channel is small.

The obvious method is to use a repetition code: repeat $x$ many times. The receiver will then use majority vote to recover $x$.

Suppose I want an overall error probability of at most $\delta$ (i.e., the probability that the receiver guesses $x$ incorrectly is at most $\delta$). How many times do I need to repeat $x$?

If $\delta$ is fixed, I can see that the number of repetitions needs to be proportional to $1/(1-h_2(p))$, where $h_2$ is the binary entropy function. My question is: what is the dependence on $\delta$?

I'm guessing we should send $c_\delta / (1-h_2(p))$ copies of $x$, for constant $c_\delta$ that depends on $\delta$; how does $c_\delta$ depend on $\delta$, asymptotically, for small values of $\epsilon,\delta$? (For example, is it something like $c_\delta \sim 1 + \log 1/\delta$?)

• The repetition code is definitely suboptimal for the BSC (general $p$), in the sense that its performance is (much) below the Shannon bound. It requires a rate that tends to 0 to attain almost 0 probability of error (instead of $1-h(p)$. May 11 '16 at 11:55

I think you are attacking the problem using the wrong conceptual frame.

The probability of decoding error for a repetition code of length $n$ (odd) corresponds to the event of majority of bit errors, that is, a Binomial:

$$\delta = \sum_{k=(n+1)/2}^{n} \binom{n}{k} (1-p)^{n-k} p^{k} \tag{1}$$

This gives $\delta$ as a function of $p$ and $n$; and in principle it allows the inverse calculation ($n$ as a function of given $\delta,p$). But, of course, it can be done only numerically.

A simplification can be done, assuming $n$ is large (then the above sum turns into the integral of a Gaussian density), and that $p=(1-\epsilon)/2$ , with $\epsilon \to 0^+$. But this is just math.

Here's the math.

The Binomial (which counts bit errors) tends to a Gaussian of mean $np$ and variance $n p (1-p)$. And the sum tends to an integral from $n/2$ to $\infty$, (Gaussian tail or Q function), hence, in this asymptotic approximation

$$\delta = Q\left(\frac{n/2-np}{\sqrt{n p (1-p)}}\right) \tag{2}$$ Given $p=(1-\epsilon)/2$, the argument is given by

$$\sqrt{n} \frac{\epsilon/2}{\sqrt{\epsilon (1- \epsilon)/4}}=\sqrt{n \frac{\epsilon^2}{ 1- \epsilon^2}} \tag{3}$$

If we further assume $0<\epsilon \ll 1$ we get

$$\delta = Q( \epsilon \sqrt{n} ) \tag{4}$$

This equation relates $\delta$, $n$, and $\epsilon$. Namely

$$n = \frac{(Q^{-1}(\delta))^2}{\epsilon^2} \tag{5}$$

If you need asymptotics, you need to specify what tends to what. This is no specified in the question body.

If you want to find $n$ such that, as $\epsilon \to 0^+$ the probability of error keeps a finite constant value $\delta$, then you just use $(5)$ - the only conclusion is that $n \epsilon^2$ must be constant.

If instead you are told that $\delta \to 0$, then you can use $({\rm inverf} x)^2 \approx \log[(1-x)/\sqrt{\pi}]$ and $Q^{-1}(a)=\sqrt 2 \, {\rm inverf}(1-2a)$ Then

$$n \approx\frac{1}{\epsilon^2} 2 \log^2 (2 \delta /\sqrt{\pi})$$

When repeating the bit $n$ times, the error probability is

$$\delta = \sum_{i=(n+1)/2}^n {n \choose i} p^i (1-p)^{n-i}.$$

The latter is a tail of the Binomial distribution and is approximately $\exp(-cn)$ where

$$c = 0.5 \lg(0.5/p) + 0.5 \lg(0.5/(1-p)).$$

This is

$$c = 0.5 \lg(1/(1-\epsilon)) + 0.5 \lg(1/(1+\epsilon))$$

which, after applying a Taylor series approximation, is approximately (for small values of $\epsilon$)

$$c \approx -0.5 \epsilon^2 / \log 2.$$

So, we find

$$\delta \approx \exp(-0.72 \epsilon^2 n).$$

It follows that we need the number $n$ of repetitions to be approximately

$$n \approx -1.39 {\log \delta \over \epsilon^2},$$

i.e., the dependence on $\delta$ is logarithmic.

Note that we have

$$h_2(p) = -0.5 \lg p - 0.5 \lg(1-p) = 1 -0.5 \lg(1-\epsilon) - 0.5 \lg(1+\epsilon).$$

By a similar Taylor series approximation, we see that

$$h_2(p) \approx 1- 0.5 \epsilon^2/\log 2,$$

so

$$1/(1-h_2(p)) = 2 {\log 2 \over \epsilon^2}.$$

Therefore, the estimate $n \sim 1/(1-h_2(p))$ was actually correct (up to a constant factor, as stated in the question). In particular, when we take into account the dependence on $\delta$, we see that we need

$$n \approx {\log \delta \over 1 - h_2(p)}.$$