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$?)
Best Answer
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}) $$