Mismatch Capacity under Stochastic Decoding

1. Problem Statement

The paper addresses the fundamental problem of mismatched decoding in information theory. In standard communication scenarios, the decoder is assumed to know the true channel transition law $W(y|x)$ and employs Maximum Likelihood (ML) decoding to minimize error probability. However, in practical situations (e.g., channel uncertainty, finite-precision arithmetic, or simplified metrics), the decoder may use a fixed, sub-optimal decoding metric $q(x, y)$ that does not match the true channel law.

The central challenge is characterizing the mismatch capacity ($C_M$)—the highest achievable rate with arbitrarily low error probability under a fixed mismatched metric. While lower bounds (like Generalized Mutual Information, GMI, and the LM rate) are well-established, a tight, general single-letter upper bound for the mismatch capacity of discrete-memoryless channels (DMCs) with maximum metric decoding remains an open problem (the Csiszár-Narayan conjecture).

This paper specifically investigates mismatched stochastic likelihood decoders. Unlike deterministic maximum metric decoders (which output the codeword maximizing $q$), a stochastic decoder outputs a message $m$ with a probability proportional to the metric value $q(x_n(m), y_n)$. The authors aim to derive a general capacity formula for this decoder and determine if it resolves the Csiszár-Narayan conjecture.

2. Methodology

The authors employ the Information-Spectrum Method, originally developed by Verdú and Han for general channels, and adapt it to the mismatched stochastic setting.

• Stochastic Decoder Definition: The decoder outputs message $m$ with probability:
  $$P(\hat{X}_n = x_n(m) | Y_n = y_n) = \frac{q_n(x_n(m), y_n)}{\sum_{\bar{m}=1}^{M_n} q_n(x_n(\bar{m}), y_n)}$$
• Mismatched Information Density: They define a normalized mismatched information density sequence:
  $$\frac{1}{n} \imath_{q_n}(X_n, Y_n) = \frac{1}{n} \log \frac{q_n(X_n, Y_n)}{\sum_{\bar{x}_n} P_{X_n}(\bar{x}_n) q_n(\bar{x}_n, Y_n)}$$
• Bounds Derivation:
  1. Feinstein-type Upper Bound: They derive an upper bound on the average error probability for random coding, showing it is bounded by the tail probability of the mismatched information density falling below the rate.
  2. Verdú-Han-type Lower Bound: They derive a converse (lower bound) on the error probability for any code, showing that if the rate exceeds the limit inferior of the information density, the error probability cannot vanish.
• Uniform Integrability: To bridge the gap between probabilistic limits (limit inferior in probability) and expectations, the authors utilize the concept of uniform integrability of the sequence of normalized information densities. This allows converting the probabilistic limit into a limit of expectations for specific channel classes.

3. Key Contributions

A. General Mismatch Capacity Formula

The primary theoretical contribution is the derivation of a general information-spectrum formula for the mismatch capacity under stochastic decoding, denoted as $\bar{C}_q(W)$:
$$\bar{C}_q(W) = \sup_{P_X} \underline{I}_q(X; Y)$$
where $\underline{I}_q(X; Y)$ is the spectral inf-mismatched information rate, defined as the limit inferior in probability of the normalized mismatched information density:
$$\underline{I}_q(X; Y) \triangleq \text{p-lim inf}_{n \to \infty} \frac{1}{n} \imath_{q_n}(X_n, Y_n)$$
This result establishes a direct parallel to the Verdú-Han formula for matched capacity, replacing the true channel likelihood with the decoding metric.

B. Tightness of the Csiszár-Narayan Conjecture for Stochastic Decoders

The paper proves that for Discrete-Memoryless Channels (DMCs) with product decoding metrics, the Csiszár-Narayan conjecture holds true for stochastic decoders.

• The authors show that the sequence of normalized mismatched information densities is uniformly integrable under mild conditions (bounded metrics).
• Consequently, the probabilistic limit inferior can be replaced by the limit of expectations.
• This leads to an achievable capacity formula expressed as the limit of multi-letter optimized rates:
  $$\bar{C}_q(W) = \lim_{k \to \infty} \sup_{P_{X^k}} \frac{1}{k} \mathbb{E} \left[ \log \frac{q_k(X^k, Y^k)}{\mathbb{E}[q_k(\bar{X}^k, Y^k) | Y^k]} \right]$$
  This confirms that the conjectured capacity (based on product-space improvements of random coding) is indeed achievable using stochastic decoders.

C. Relationship with Maximum Metric Decoding

The authors demonstrate that the mismatch capacity under stochastic decoding is a lower bound on the mismatch capacity under deterministic maximum metric decoding ($C_{mm}^q$).
$$\bar{C}_q(W) \leq C_{mm}^q(W)$$
This aligns with intuition, as the stochastic decoder is a randomized version of the maximum metric decoder. However, for DMCs with product metrics, the stochastic decoder achieves the same capacity as the conjectured maximum metric capacity.

D. Generalization to Tilting and Transformations

The analysis is extended to generalized stochastic decoders where the metric is transformed by a non-decreasing function $f(q_n)$. The paper shows that applying a "tilting" parameter $\alpha \geq 1$ (i.e., using $q^\alpha$) can potentially improve the achievable rate, though the capacity formula structure remains similar.

4. Key Results

1. Error Probability Bounds: The paper establishes that for any codebook, the error probability is tightly bounded by the probability that the normalized mismatched information density falls below the code rate (plus/minus a small $\gamma$).
2. Capacity Equivalence: For DMCs and product metrics, the mismatch capacity is the limit of the optimized $k$-letter Generalized Mutual Information (GMI) or LM rate as $k \to \infty$.
3. Strong Converse: The paper establishes conditions under which the strong converse property holds (error probability goes to 1 if rate exceeds capacity).
4. Upper Bound via Expectations: When the information density sequence is uniformly integrable, the capacity is upper-bounded by the limit of the expected mismatched information density. This upper bound is shown to be achievable for DMCs.

5. Significance

• Resolution of an Open Problem: The paper provides a significant step toward resolving the long-standing Csiszár-Narayan conjecture. While the conjecture remains open for deterministic maximum metric decoders in the general case, this work proves it is tight for stochastic likelihood decoders. This suggests that the "gap" in the conjecture might be an artifact of the deterministic decoding constraint rather than the channel/metric mismatch itself.
• Simplified Analysis: By utilizing stochastic decoders, the authors derive capacity formulas and bounds that are mathematically simpler (avoiding complex union bounds associated with deterministic max-min operations) while retaining the same capacity and error exponents as ML decoding in the matched case.
• Unified Framework: The work unifies the treatment of mismatched decoding under the information-spectrum framework, providing a general formula applicable to arbitrary channels and metrics, not just DMCs.
• Practical Implications: The results validate the use of product-space improvements (increasing the block length of the code used for metric calculation) to approach the true mismatch capacity, offering a theoretical basis for designing robust coding schemes for channels with imperfect knowledge.

In summary, this manuscript advances the theoretical understanding of mismatched decoding by proving that stochastic likelihood decoders achieve the Csiszár-Narayan capacity limit for DMCs, thereby providing a complete information-spectrum characterization of mismatch capacity under this decoding paradigm.