🔢 mathematics

On the exact decoding error probability exponent of the random coding on BSC

This paper derives the exact decoding error probability exponent for random coding over a binary symmetric channel with an exponential number of messages, utilizing new results on the distribution of a specific sum of random variables.

Original authors: Marat V. Burnashev

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marat V. Burnashev

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy room. This room is what mathematicians call a Binary Symmetric Channel (BSC). In this room, every time you whisper a "0" or a "1," there is a small chance the wind (noise) will flip it to the opposite sound.

Now, imagine you aren't just sending one message; you are sending a massive library of messages at once. To make sure the listener can tell them apart, you create a giant list of unique "codes" (like long strings of 0s and 1s). You pick these codes randomly, like drawing names from a hat.

The big question this paper answers is: How fast does the chance of making a mistake drop as you make your messages longer?

If you send a short message, the wind might easily confuse it. But if you send a very long message, the listener can usually figure out what you meant, and the chance of error becomes tiny. The paper calculates the exact "speed" at which this error probability shrinks to zero. This speed is called the error exponent.

The Three Zones of Communication

The author, M. V. Burnashev, discovered that the relationship between how much information you send (the "Rate") and how likely you are to make a mistake isn't a single straight line. Instead, it behaves like a road with three distinct sections, separated by two critical "speed bumps" or thresholds.

Think of the Rate as how crowded the room is with messages.

1. The "Low Traffic" Zone (Very Low Rates)

When you are sending very few messages compared to the length of the code, you have plenty of room to maneuver.

The Analogy: Imagine you are in a huge, empty parking lot. You can park your car (your message) anywhere, and it's very easy to find it later.
The Result: In this zone, the error probability drops incredibly fast. The paper provides a new, precise formula for this speed. It turns out that for these low rates, the error drops even faster than previous theories suggested. It's like having a "super-power" of clarity when you aren't trying to send too much data.

2. The "Moderate Traffic" Zone (Medium Rates)

As you start sending more messages, the parking lot gets a bit crowded. You have to be more careful where you park.

The Analogy: The lot is filling up. You can still find your car easily, but you have to look a bit harder. The "noise" of the room starts to matter more.
The Result: In this middle section, the speed at which errors disappear changes its character. The paper identifies a specific "tipping point" (called $R_{crit}$ ) where the behavior shifts. Before this point, the error drops very fast; after this point, it slows down slightly. The author gives a new, exact formula for this transition, fixing a gap in previous math that only gave rough estimates.

3. The "High Traffic" Zone (High Rates)

Now you are trying to send a huge number of messages. The parking lot is packed.

The Analogy: The lot is full. Cars are parked bumper-to-bumper. If the wind blows a car slightly, it's hard to tell which car is yours.
The Result: This is the "classic" zone that mathematicians have known about for a long time. The error probability still drops, but it follows a well-known, slower pattern. The paper confirms that for these high rates, the old formulas were correct, but it proves that the "weird" behavior happens only in the first two zones.

The "Magic" Discovery

Before this paper, mathematicians knew the rules for the "High Traffic" zone perfectly. For the "Low Traffic" zone, they knew there were special codes that performed better than the average, but they didn't have a single, clean formula to describe the average performance of a random code.

Burnashev's paper is like finding the missing piece of a puzzle. He derived a single, exact formula that works for all rates, from the empty parking lot to the packed one.

He did this by looking at a specific mathematical "sum" (a way of adding up probabilities). He proved that this sum behaves in a very predictable way, almost like a law of nature, which allowed him to calculate the exact error rate without needing to guess or use approximations.

Why This Matters (According to the Paper)

The paper doesn't talk about building new phones or satellites. Instead, it solves a fundamental math problem: How do we describe the limits of random communication?

It removes the "Parametric" headache: Previous formulas for the middle zone were "parametric," meaning you couldn't just plug in a number and get an answer; you had to solve a complex side equation first. Burnashev's formulas are direct. You plug in the noise level and the rate, and you get the answer.
It corrects the "Low Rate" myth: It shows that the "weakness" of random codes at low speeds isn't a flaw in the codes themselves, but a flaw in the old math used to measure them. The codes are actually much better than we thought.

In short, this paper draws a perfect map of how likely you are to make a mistake when sending random messages through a noisy channel, covering every possible speed from slow to fast, with a new, precise set of rules for the slow and medium speeds that no one had written down exactly before.

Technical Summary: On the Exact Decoding Error Probability Exponent of the Random Coding on BSC

Problem Statement
The paper addresses the fundamental problem of determining the exact asymptotic behavior of the decoding error probability for random coding over a Binary Symmetric Channel (BSC) with crossover probability $p$ ( $0 \le p \le 1/2$ ). Specifically, it investigates the random coding exponent, $E_r(R)$ , defined as the exponential decay rate of the expected decoding error probability for a code of block length $n$ and rate $R$ as $n \to \infty$ . While the exponent is well-understood for rates above the critical rate $R_{cr}(p)$ , the behavior at low rates ( $R < R_{cr}(p)$ ) has historically been described only by lower bounds, leaving the exact asymptotic form an open question.

Methodology
The author employs a probabilistic analysis of the posterior probabilities in a maximum likelihood decoding scenario. The core methodology involves:

Posterior Probability Formulation: The decision rule is framed in terms of posterior probabilities $\pi_i$ . An error occurs if the posterior probability of the transmitted codeword $\pi_m$ falls below $1/2$ , which is equivalent to the condition that the sum of weighted distances of all other codewords exceeds the weighted distance of the transmitted codeword.
Analysis of Random Sums: The proof relies on the distribution of a random sum $S(z, M, n) = \sum_{j=1}^M z^{d(y, x_j)}$ , where $z = p/q$ and $d$ is the Hamming distance. The author utilizes a previously established result (Theorem 2 from reference [7]) regarding the concentration of this sum around its mean, $M z^{n/2}$ , with high probability.
Asymptotic Maximization: The error probability is expressed as an expectation over the distance of the transmitted codeword. The exponent is derived by maximizing a specific function $f_2(p, R, b)$ over the possible normalized distances $b$ . This maximization is split into cases based on the relationship between the rate $R$ , the critical rate $R_{cr}(p)$ , and a newly defined rate $R_{crit}(p)$ .

Key Contributions and Results
The primary contribution is the derivation of the exact formula for the random coding exponent $E_r(R)$ for all rates $0 \le R \le C(p)$ , resolving the ambiguity that previously existed for low rates.

The paper introduces a new critical rate, $R_{crit}(p)$ , defined as:
$R_{crit}(p) = (\sqrt{q} - \sqrt{p})^2 \frac{\ln(q/p)}{2(\sqrt{q} + \sqrt{p})}$
where $q = 1-p$ . It is shown that $R_{crit}(p) < R_{cr}(p)$ for $0 < p < 1/2$ .

The exact exponent $E_r(R)$ is given by a piecewise function $g(p, R)$ :

Low Rate Region ( $0 \le R \le R_{crit}(p)$ ):
$E_r(R) = 2R - \ln 2 + 2h(r_0) + \ln(\sqrt{pq})$
where $r_0 = \frac{1}{2} + \frac{R}{\ln(p/q)}$ and $h(x)$ is the binary entropy function.
Intermediate Rate Region ( $R_{crit}(p) \le R \le R_{cr}(p)$ ):
$E_r(R) = \ln 2 - 2\ln(\sqrt{q} + \sqrt{p}) - R$
High Rate Region ( $R_{cr}(p) \le R \le C(p)$ ):
$E_r(R) = E_{sp}(R)$
where $E_{sp}(R)$ is the standard sphere-packing exponent.

Significance and Claims
The paper positions itself as a supplement to prior work (specifically reference [5]) that investigated whether the weakness of $E_r(R)$ at low rates was an artifact of bounding techniques. By providing the exact asymptotic, the author demonstrates that the previously known lower bounds were indeed loose for the random coding exponent in the low-rate regime.

The author highlights two specific points of significance:

Exactness vs. Bounds: While relations for $R \ge R_{crit}(p)$ were known to be lower bounds, this paper establishes the exact equality for the entire range of rates.
Non-Parametric Form: Citing R. Gallager's observation that $E_r(R)$ for the BSC was previously only expressible in parametric form, the author notes that the derived formulas (8)–(10) provide a direct, non-parametric expression for the exponent, provided the natural representation $R = \ln 2 - h(\delta_R)$ is accepted.

The paper concludes that the derived formula $g(p, R)$ represents the exact asymptotic of the random coding exponent for the BSC, filling a gap in the theoretical understanding of channel coding limits at low rates.