Reliability Function of the Binary Symmetric Channel Below the Critical Rate

Reliability Function of the Binary Symmetric Channel Below the Critical Rate

Definitions and mathematical statement

A binary symmetric channel independently flips each bit with probability $p\in(0,1/2)$ and gives no feedback. Let $P_e^*(n,R,p)$ be the minimum average maximum-likelihood block error over binary length-$n$ codes with at least $\lceil2^{nR}\rceil$ equiprobable messages. Define \[ E(R,p)=\limsup_{n\to\infty}-\frac1n\log_2P_e^*(n,R,p), \quad R_{\mathrm{crit}}(p)=1-H_2\!\left(\frac{\sqrt p}{\sqrt p+\sqrt{1-p}}\right), \] where $H_2(t)=-t\log_2t-(1-t)\log_2(1-t)$. Determine $E(R,p)$ for every $0<R<R_{\mathrm{crit}}(p)$. This requires matching achievable and converse exponents, or an equivalent evaluable exact characterization, not simply restating the optimization or assuming its limsup is a limit.

Formulation and concept references: [S1].

Short English statement

Below the binary symmetric channel's critical rate, what is the best possible exponential decay rate of block error for long codes without feedback?

Research attempt

Scope and literature check.

This attempt was prepared by GPT-6 Astra Ultra on 27 September 2026. All logarithms in exponents below have base two. The source [S1] already proves exactness of the random-coding exponent on a nonempty interval immediately below the critical rate. Thus it would be incorrect to describe every rate in the requested interval as wholly unsettled. The present work independently derives explicit achievable and converse bounds and the positive-rate zero-rate limit; it does not claim to determine the entire remaining reliability curve.

Write \[ Z=2\sqrt{p(1-p)},\qquad d_p=-\log_2 Z>0, \qquad D_2(q\Vert p)=q\log_2\frac qp+(1-q)\log_2\frac{1-q}{1-p}. \] In particular $d_p=D_2(1/2\Vert p)$. Let $\delta_R\in(0,1/2)$ satisfy $H_2(\delta_R)=1-R$ when $0<R<1$. The attack is to compare distance-based achievability with a decoding region converse and identify exactly where they cease to match.

Message count and tie conventions.

It suffices to optimize over exactly $M=\lceil2^{nR}\rceil$ distinct codewords. Indeed, from a larger code choose the $M$ messages with smallest conditional errors under its optimum decoder. On outputs which were decoded to a deleted message, choose any retained message; success for the retained messages does not decrease. Maximum-likelihood decoding on the subcode does at least as well. Thus deleting messages cannot invalidate this reduction for average error.

Ties may be broken deterministically or at random. For two codewords at distance $d$, the optimum equiprobable binary error is \[ B_d=\Pr\{\operatorname{Bin}(d,p)>d/2\} +\tfrac12\Pr\{\operatorname{Bin}(d,p)=d/2\}. \tag{1} \] Only the $d$ differing coordinates affect the likelihood ratio. Chernoff's bound, using the likelihood-ratio parameter which balances $p$ and $1-p$, gives $B_d\le Z^d$. A bound in the other direction is also useful: \[ B_d\ge \frac{c_p}{d+1}Z^d\quad(d\ge1), \tag{2} \] with $c_p>0$ depending only on $p$. For even $d$, keep the central term in $1$, use $\binom d{d/2}\ge2^d/(d+1)$, and take $c_p\le1/2$. For odd $d$, keep the term with $(d+1)/2$ flips; its extra factor is $\sqrt{p/(1-p)}$, so take the smaller of these two positive constants. These estimates preserve the tie contribution and show that the pair exponent is $d\,d_p$, up to logarithmic terms.

A direct random-code bound.

For any code $C$, the union bound over pairwise likelihood comparisons gives \[ P_e(C)\le\frac1{|C|}\sum_{x\in C}\sum_{y\in C\setminus\{x\}}Z^{d(x,y)}. \tag{3} \] For a uniformly random ordered distinct pair of binary words, \[ \mathbb E Z^{d(x,y)} =\frac{(1+Z)^n-1}{2^n-1}. \tag{4} \] This follows by fixing $x$ and summing $\binom njZ^j$ over $1\le j\le n$. A random $M$-subset therefore has expected bound $(M-1)((1+Z)^n-1)/(2^n-1)$. Some code attains at most this value, so, also using the trivial nonnegativity of the exponent, \[ E(R,p)\ge\max\{0,1-R-\log_2(1+Z)\}. \tag{5} \] No independence between all pair distances is needed for this expectation calculation.

Expurgation with a free parameter.

Fix $\rho\ge1$ and start with a uniformly random $L=2M$-subset, which is possible for all large $n$ at fixed $R<1$. For each codeword set \[ A_x=\sum_{y\ne x} Z^{d(x,y)/\rho}. \] The expected average of $A_x$ equals \[ (L-1)\frac{(1+Z^{1/\rho})^n-1}{2^n-1}=:K_n. \] Choose a code whose average is at most $K_n$ and discard the half with largest $A_x$. At least $M$ remain, each with $A_x\le2K_n$. For nonnegative numbers $a_j$ and $\rho\ge1$, $\sum_j a_j^\rho\le(\sum_j a_j)^\rho$. Consequently $3$, now on the retained subcode, gives $P_e\le(2K_n)^\rho$. For each fixed $\rho$ this proves \[ E(R,p)\ge E_{\rm ex}(R,p):= \sup_{\rho\ge1}\rho\left(1-R-\log_2(1+Z^{1/\rho})\right). \tag{6} \] The supremum can be combined with zero. The proof chooses the code separately for each $n$ and fixed $\rho$; it does not exchange an unjustified limit with a varying optimizing parameter. At $\rho=1$ it includes $5$. This is the familiar expurgation mechanism, derived here to make the distance and averaging steps explicit.

A sphere-counting converse for average error.

Fix $q$ with $\delta_R<q<1/2$ and put $k=\lfloor nq\rfloor$. For each transmitted codeword there are $\binom nk$ outputs at exactly distance $k$, all with channel probability $p^k(1-p)^{n-k}$. Among the $M\binom nk$ ordered message-output incidences in this shell, at most $2^n$ can be decoded correctly, since each output can name only one message. Randomized decoding gives the same inequality for the sum of success probabilities. Therefore \[ P_e(C)\ge \left(1-\frac{2^n}{M\binom nk}\right) \binom nk p^k(1-p)^{n-k}. \tag{7} \] The parenthesis tends to one exponentially, because $R+H_2(q)>1$. The elementary type bounds \[ \frac{2^{nH_2(k/n)}}{n+1}\le\binom nk\le2^{nH_2(k/n)} \] show that the last product has exponent $D_2(q\Vert p)$. The bound is uniform over the code, so it survives minimization and the limsup in the definition. Letting $q\downarrow\delta_R$ yields \[ E(R,p)\le D_2(\delta_R\Vert p) \tag{8} \] in the range $R<1-H_2(p)$, in particular throughout the question's range. The restriction matters: taking $q<p$ would not give the usual positive sphere-packing exponent in the same manner.

A second converse and a sharp limiting consequence.

For $M$ binary words, the total distance over all unordered pairs is at most $nM^2/4$: at each coordinate, the number of disagreeing pairs is $a(M-a)\le M^2/4$. Hence some pair has \[ d\le\frac{nM}{2(M-1)}. \tag{9} \] For any decoder for the full code, its two conditional errors on that pair have sum at least $2B_d$, since a binary optimum can only improve their combined success. Thus $P_e(C)\ge2B_d/M$. Combining $2$ and $9$, then taking $n\to\infty$ at fixed positive $R$, proves \[ E(R,p)\le R+\frac{d_p}{2}. \tag{10} \] Although usually weaker than refined converses, this is enough to pin down the right-hand limit at zero rate. For fixed $\rho$ the right side of $6$ is continuous in $R$, while \[ \lim_{\rho\to\infty} \rho\left(1-\log_2(1+Z^{1/\rho})\right)=d_p/2. \] This follows by differentiating $\log_2(1+2^{-d_p/\rho})$ at $1/\rho=0$. First choose a large fixed $\rho$ and then let $R\downarrow0$. Equations $6$ and $10$ give \[ \lim_{R\downarrow0}E(R,p)=d_p/2.\tag{11} \] This does not evaluate the literal definition at $R=0$: that definition allows one message and zero error. Nor does it equal the two-message repetition exponent $d_p$. The order of quantifiers is essential.

Where distance bounds lose information.

For a fixed message, pairwise error events overlap. Their union cannot be replaced by their sum in a converse. The subtractive second-order terms depend on triples of codewords, not only on the minimum distance. Conversely, one close pair may account for only $2/M$ of all messages; dropping that factor incorrectly removes the $R$ in $10$. The distance-distribution approach in [S1] addresses this distinction, but its exactness interval is not a proof for every smaller rate.

Our bounds leave a visible gap at typical interior low rates. A plot or a numerical maximization of $6$ would merely compare proved bounds, not identify the optimum code family or certify equality. An exact finite check can enumerate all binary words for small $n$, verify $4$, compute $1$ as a rational number for rational $p$, and compare actual decoding errors with $3$. The accompanying script does these algebraic checks; no asymptotic equality is inferred from them.

Final status.

UNRESOLVED. Equations $6$, $8$, $10$, and the limiting value $11$ are established here. The full requested function for every $0<R<R_{\rm crit}$ is not determined. The first missing step is a matching converse or construction at rates where these bounds differ. Concrete targets are a lower bound on error involving a substantial fraction of messages, control of intersections of pairwise error events, and a family of codes attaining the resulting exponent. We have not proved existence of a limit in place of the specified limsup.

Sources

• S1 Barg and McGregor, Distance distribution of binary codes and the error probability of decoding. https://arxiv.org/pdf/cs/0407011. Formulation source.