PaperlayerView exact revision on arXiv

Source-linked AI summary

Soft GRAND under Channel Uncertainty: Minimax Posterior-Envelope Ordering and Gallager-Exponent Preservation

Behrooz Razeghi

arXiv:2609.29688v1cs.ITmath.IT

TL;DR

Under channel uncertainty, matched Soft GRAND orders can disagree, so a single observation-dependent correction order must serve across admissible posteriors. The paper uses posterior-envelope ordering and establishes conditions for preserving matched rank moments and fixed-rate error exponents. For uniform-input memoryless channels, the resulting exponent equals Gallager’s uniform-input random-coding exponent.

  • Problem

    Admissible channels can assign different matched ranks to the same correction at the same observation, and pointwise minimax rank regret alone does not determine the uniform-subset ensemble-average error exponent.

    Source: §1 · p. 1

  • Method

    The paper orders corrections by a posterior envelope and gives sufficient tilt-closure and conditional Shtarkov-complexity conditions for preserving the matched rank-moment spectrum.

    Source: §1 · p. 3, §10 · p. 43

  • Results

    Under the stated differentiability and entropy nondegeneracy conditions, the auxiliary order attains the matched uniform-subset ensemble-average error exponent at every fixed rate strictly between zero and one.

    Source: §1 · p. 3, §10 · p. 44

  • Takeaways & Limitations

    For uniform-input memoryless channels, the matched uniform-subset ensemble-average error exponent equals Gallager’s uniform-input random-coding exponent.

    Source: §1 · p. 3, §10 · p. 43

    A fixed-weight mixture of conditional posteriors used in the assignment construction need not equal the posterior induced by the corresponding mixture of channels.

    Source: §5.2 · p. 19

Abstract

from arXiv · show

Soft Guessing Random Additive Noise Decoding queries corrections in an observation-dependent order. For a known channel, the matched order ranks corrections by nonincreasing conditional posterior probability. Under channel uncertainty, admissible channels may induce matched orders that assign different ranks to the same correction at the same observation. We instead use a posterior-envelope order, defined by the pointwise supremum of codebook-independent uniform-input correction posteriors. For fixed measurable posterior representatives and a measurable envelope, this order minimizes, at each observation, the worst-case logarithm of the rank--posterior product over admissible channel--correction pairs with positive posterior probability. For uniform-subset codebooks, this finite-block minimax property does not by itself determine the ensemble-average error exponent, which depends on the distribution of the realized correction rank. For i.i.d. correction--observation pairs with a finite correction alphabet whose joint distribution is dominated by the product of counting measure on that alphabet and a $\sigma$-finite measure on the observation space, Arimoto conditional R\'enyi entropy characterizes the matched rank-moment spectrum. An auxiliary posterior-envelope order preserves this spectrum on $[0,1]$ when its posterior family contains the corresponding conditional power tilts and has subexponential conditional Shtarkov complexity on observation sets whose complement probabilities decay exponentially faster than the reciprocal correction-space cardinality. Under additional differentiability and entropy nondegeneracy conditions, the auxiliary order attains the matched uniform-subset ensemble-average error exponent at every fixed normalized code rate strictly between zero and one. For uniform-input memoryless channels, this exponent equals Gallager's uniform-input random-coding exponent.

1 Introduction

The paper formulates Soft GRAND under channel uncertainty as an observation-wise minimax choice of correction order, then treats finite-block rank regret and fixed-rate ensemble-average error exponents as distinct criteria. It gives conditions under which posterior-envelope ordering preserves the matched rank-moment spectrum and error exponent.

1 Introduction

  • For uniform-subset codebooks, pointwise minimax rank regret alone does not determine the fixed-rate ensemble-average error exponent, which depends on the realized-rank distribution.An exact rank–collision identity relates the ensemble-average error probability to that distribution, including its right tail.Source: §1 · pp. 2–3
  • The posterior-envelope order minimizes worst-case posterior-normalized rank regret at each admissible observation, with an exact pointwise minimax value.The corresponding conditional Shtarkov minimax log-loss regret exceeds this value by at most O(log n).Source: §1 · p. 3
  • For i.i.d. correction–observation pairs with a finite correction alphabet, Arimoto conditional Rényi entropy characterizes the matched positive rank-moment spectrum.The stated setting assumes the joint distribution is dominated by counting measure on the correction alphabet times a σ-finite measure on the observation space.Source: §1 · p. 3
  • An auxiliary posterior-envelope order preserves the matched rank-moment spectrum on [0, 1] under tilt-closure and subexponential conditional Shtarkov-complexity conditions.With the stated differentiability and entropy nondegeneracy conditions, it attains the matched uniform-subset ensemble-average error exponent at every fixed rate strictly between zero and one.Source: §1 · p. 3
  • For uniform-input memoryless channels, the preserved matched ensemble-average error exponent equals Gallager’s uniform-input random-coding exponent.The decoder posterior family may include auxiliary posteriors not induced by channels in the prescribed class.Source: §1 · p. 3
  • For generalized-Gaussian BPSK with uncertain shape and scale, changing scale at fixed shape leaves the correction order unchanged, while changing shape can reverse pattern order.The posterior-grid and exponent-preservation conditions are verified for this example.Source: §1 · p. 3

2 Related Work

Prior work studies universal decoding, guessing under specified source models or source uncertainty, and observation-dependent GRAND orders built from specified channel or reliability information. This paper instead selects one deterministic correction permutation per observation against a family of conditional posteriors, using pointwise minimax rank regret and separate conditions for exponent preservation.

2 Related Work

  • Conditional-guesswork and source-uncertainty work characterizes moments, tails, or guessing strategies under source models, rather than the paper’s observation-wise deterministic permutation choice.The related formulations include conditional guesswork exponents [16], source uncertainty, and mismatched guesswork.Source: §2 · p. 4
  • Universal GRAND and noise-guessing studies address discrete additive channels or prescribed sequence metrics, whereas this work allows soft observations that may be continuous.The cited works include universal GRAND, noise-sequence probability estimators [7], and mismatched noise-guessing analyses [8].Source: §2 · p. 4
  • ORB-type orders use specified reliability information or induced distributions, unlike pointwise minimax optimization over a family of conditional posteriors.The cited analyses include achievable-rate and capacity comparisons, finite-length bounds, and exact block-error or test-count expressions [9] [10].Source: §2 · pp. 4–5
  • Methods exploiting channel memory, correlation, or switching build orders from specified, estimated, or tracked channel or posterior information.Examples include Markov-noise, correlated-channel, finite-memory-posterior, switching-and-drift, and fading-estimation approaches [11] [12] [13] [37].Source: §2 · p. 5
  • Shtarkov and contextual normalized-maximum-likelihood methods optimize probability assignments under log loss, whereas this finite-block problem optimizes a correction permutation under posterior-normalized rank regret.The comparison also distinguishes sequential minimax-regret bounds based on sequential square-root entropy.Source: §2 · p. 5

3 Channel Model and Posterior-Ordered Soft GRAND

The model uses a finite Abelian-group input and permits general soft observations carrying receiver-side information. A codebook-independent uniform-input correction posterior gives the matched likelihood order for a known channel, while Universal Soft GRAND chooses an observation-dependent correction permutation independently of the channel realization and codebook.

3.1 Finite input, general soft observation

  • The input alphabet is a finite Abelian group, and the receiver observation may include channel outputs, state estimates, and pilot-derived statistics.The observation lies in a standard Borel space, and no conditional independence among components of a composite observation is assumed.Source: §3.1 · p. 5
  • The uncertainty model fixes measurable channel densities relative to a common σ-finite measure; pointwise posterior envelopes use these representatives.For an uncountable channel class, the global finite-block minimax criterion uses the μ_n-essential supremum and is unchanged by modifications on a common μ_n-null set.Source: §3.1 · p. 6

3.2 Uniform-input correction posterior

  • Under a known channel, ordering corrections by nonincreasing uniform-input correction posterior makes the first codeword found an ML codeword.The posterior and candidate-word likelihood weak orderings coincide because their likelihoods differ by a common positive normalization factor.Source: §3.2 · p. 6
  • Changing the codebook-independent reference decision relabels correction posteriors by a permutation and preserves their probability multiset and matched ordering, up to ties.The likelihood weak ordering of corresponding candidate words is unchanged.Source: §3.2 · p. 7

3.3 Universal Soft GRAND

  • Universal Soft GRAND selects a measurable codebook-independent correction permutation for each observation, with the codebook entering only through membership testing.The query order may depend on the prescribed channel class and observation, but not on the unknown channel or codebook.Source: §3.3 · p. 7
  • Rank-distribution statements use the auxiliary uniform-input experiment, while a fixed deterministic codebook can induce a different conditional correction distribution.Under the uniform-subset ensemble, averaging over codebooks and uniform transmitted messages recovers the auxiliary joint distribution.Source: §3.3 · p. 8

4 Conditional Query Rank and First-Order Universality

Section 4 characterizes first-order query-rank behavior through conditional posterior self-information, Kraft-admissible assignments, and posterior-universal ordering. It also treats memoryless soft-information compression and one-shot conditions for preserving the minimum query-rank exponent.

4.1 Conditional Posterior AEP

  • Under a conditional posterior AEP, posterior self-information converges in probability to h(W), which lies between zero and one.For finite-alphabet stationary ergodic pairs, the AEP follows from the Shannon–McMillan–Breiman theorem; in the memoryless setting it follows from convergence of sample averages.Source: §4.1 · p. 8

4.2 Conditional Kraft assignments

  • Conditionally Kraft-admissible codelengths bound query rank, and a posterior-universal conditional pmf supplies such codelengths through its negative logarithm.The conditional Kraft rank bound applies to the order by nondecreasing codelength; for a conditional pmf Q_n, L_n(e|r) = −log Q_n(e|r) meets the Kraft condition with equality.Source: §4.2 · p. 9

4.3 Converse for observation-dependent orderings

  • Every deterministic, measurable, codebook-independent observation-dependent order obeys a first-order rank-exponent lower bound, while a common posterior-universal assignment attains the class minimax exponent.The minimax ordering may depend on the prescribed class, but not on its unknown channel.Source: §4.3 · pp. 10–11

4.4 Memoryless channels and soft-information compression

  • With symbolwise statistic S and h(R) measurable from S, the minimum first-order query-rank exponent among S-based orders is H_U,W(X|S).A common posterior-universal assignment for the conditional posteriors given S is a sufficient condition for one S-based ordering to attain that exponent across a channel class.Source: §4.4 · p. 12

4.5 One-shot posterior-rank bounds and sufficient statistics

  • One-shot bounds relate query rank to posterior self-information, while deterministic compression preserves the minimum exponent exactly when P_W(X|R) = P_W(X|S) almost surely.The posterior equality is evaluated under the uniform-input distribution.Source: §4.5 · p. 14

5 Finite-Block Minimax Posterior-Normalized Rank Regret

The posterior-envelope order minimizes worst-case posterior-normalized rank regret at each observation. The section relates this finite-block criterion to Shtarkov regret and gives conditional assignments with regret bounds under stated assumptions.

5 Finite-Block Minimax Posterior-Normalized Rank Regret

  • The posterior-envelope order attains the exact pointwise minimax posterior-normalized rank criterion by ordering corrections in nonincreasing envelope value.This gives a finite-block minimax guarantee, not by itself preservation of the matched error exponent.Source: §5 · p. 15

5.1 Posterior-envelope NML and Shtarkov regret

  • Posterior-envelope NML induces a minimax order, while conditional Shtarkov minimax log-loss regret exceeds posterior-rank regret by at most log H_n.The NML assignment attains the minimax value; the blockwise definition does not provide a recursive query-order procedure without evaluating envelope values.Source: §5.1 · p. 16, §5.2 · p. 18

5.2 Conditional-assignment constructions

  • A fixed-weight mixture of conditional posteriors need not be the posterior of the corresponding channel mixture.The construction is defined on a common observation domain and extended by a fixed conditional pmf outside it.Source: §5.2 · p. 19
  • Parameter-estimation error alone does not bound posterior log-ratios without regularity relating parameter distance to those ratios..Source: §5.2 · p. 19
  • For a finite channel class, a posterior mixture gives a blocklength-independent regret bound, and equal weights make both stated upper bounds log K..Source: §5.2 · pp. 18–19
  • For finite-dimensional classes, the stated covering and log-Lipschitz assumptions yield logarithmic regret bounds as blocklength grows.With an 1/n net and the stated finite-dimensional assumptions, the bound is L + q log(An).Source: §5.2 · pp. 20–21

6 Uniform-Subset Random Coding and First-Order Reliability

The section relates uniform-subset decoding errors to the realized correction rank, then gives first-order reliability results for fixed channels and uniform-input memoryless channels. In the memoryless case, the stated rate threshold is the uniform-input mutual information.

6.1 Uniform-subset random codebooks

  • Theorem 8 gives an exact finite-block identity linking uniform-subset ensemble error to collisions among corrections preceding the realized correction rank.Conditioned on rank d, the competing corrections form a hypergeometric sample, and the error probability is the complement of the zero-collision probability.Source: §6.1 · pp. 21–22
  • The rank union bound uses the realized correction rank to bound ensemble error, with the bound nondecreasing in rank.The supplied proof passage identifies this monotonicity as the step yielding the stated bound.Source: §6.1 · p. 22
  • For a fixed channel, Theorem 9 establishes first-order achievability for orders induced by conditionally Kraft-admissible codelengths.The theorem is stated in the uniform-subset random-codebook setting.Source: §6.1 · p. 22
  • For uniform-input memoryless channels, the stated first-order rate threshold is I_U,W(X;R)=1−H_U,W(X|R).The section also states I_U,W(X;R)≤C(W), with equality precisely when uniform input attains the supremum defining C(W).Source: §6.1 · pp. 22–23

7 Matched Positive Rank Moments and Error Exponents

The section relates matched positive rank moments to Arimoto conditional Rényi entropy and fixed-rate uniform-subset error exponents, then shows that under conditional tilt-closure and regularity conditions an auxiliary envelope order preserves the matched rank-moment spectrum and ensemble-average error exponent. This does not establish lower-tail rank asymptotics or, by itself, exponent preservation for finite posterior-grid orders.

7 Matched Positive Rank Moments and Error Exponents

  • Normalized log-rank convergence alone does not determine the fixed-rate exponent: a modified order can preserve that limit yet have a strictly smaller exponent.Example 1 constructs such an order by reversing ranks on an event of probability a^-nγ, where 0 < γ < Em.Source: §7 · p. 23, §7.1 · pp. 29–30

7.1 Matched positive rank moments

  • For i.i.d. finite-alphabet correction–observation pairs under the stated dominated standard-Borel condition, the matched positive rank-moment spectrum is characterized by Arimoto conditional Rényi entropy.The conditional entropy is continuous at order one, with the spectrum’s right derivative at zero equal to H(X|S).Source: §7.1 · pp. 24–25
  • The matched correction rank has the same conditional distribution as the matched input rank, and its moment spectrum yields Gallager’s uniform-input E0 relation.The correction mapping is a bijective relabeling conditional on the observation; deterministic tie-breaking within posterior-tie classes leaves the distribution unchanged.Source: §7.1 · pp. 26, 30
  • Under continuous differentiability of Λm on [0, 1 + ϵ] and 0 < h = H(X|S) < 1, the uniform-subset ensemble has the classical uniform-input random-coding exponent, despite its different finite-block collision kernel.Source: §7.1 · pp. 26, 30

7.2 Conditional tilt closure and Gallager exponent preservation

  • Section 7.2 introduces conditional tilt closure: the decoder’s measurable posterior family must contain the conditional power tilts associated with matched moments over a specified range of ρ.It defines the product-family posterior envelope and its conditional Shtarkov normalizer for the auxiliary ordering.Source: §7.2 · pp. 30–31
  • Theorem 12 addresses rank-moment spectrum preservation under conditional tilt closure, assuming V is ρ̄-tilt closed at θ and introducing κ > ρ̄ and measurable sets Tn.Source: §7.2 · p. 31
  • At every fixed normalized rate 0 < Rc < 1, the envelope-order and matched-order ensemble-average error exponents exist and are equal, preserving the uniform-input Gallager random-coding exponent.The theorem assumes 1-tilt closure, the stated measurable-set conditions, continuous differentiability of the matched spectrum on [0, 1 + ϵ], and 0 < Hθ(E|R) < 1.Source: §7.2 · p. 33
  • Theorem 13 does not establish lower-tail rank asymptotics or a complete rank large-deviation principle, and finite posterior-grid orders need a separate exponential-scale approximation argument for exponent preservation.Source: §7.2 · p. 34

8 Generalized-Gaussian BPSK with Order Reversal and Tilt Closure

The section shows that channel uncertainty can reverse matched correction orders, then develops posterior-grid and tilt-closed decoder families for generalized-Gaussian BPSK. Under the stated tilt-closure, differentiability, and entropy conditions, the auxiliary order preserves the matched exponent across fixed rates strictly between zero and one.

8.1 BPSK-AWGN with unknown variance

  • For BPSK-AWGN with unknown block-constant variance, the matched query permutation is independent of σ² under the prescribed tie-breaking rule.The positive factor 2/σ² does not change the weak ordering of correction patterns.Source: §8.1 · p. 34

8.2 Order reversal under unknown generalized-Gaussian shape

  • Changing the generalized-Gaussian shape parameter can reverse the relative order of two correction patterns for the same received block.For 1≤β≤2, posterior-grid mixtures also provide rank-regret bounds and posterior universality, supporting first-order query-rank achievability.Source: §8.2 · pp. 34, 35, 37
  • The generalized-Gaussian rank-regret theorem is restricted to shape parameters β≥1 and does not cover β<1.Source: §8.2 · p. 37

8.3 Tilt closure for generalized-Gaussian BPSK

  • For generalized-Gaussian BPSK, the expanded decoder posterior family yields matched Gallager-exponent preservation under uniform-subset coding at every fixed rate 0<Rc<1.The theorem uses a decoder parameter range extending to eσ+≥2^(1/β−)σ+ and establishes 1-tilt closure, differentiability, and 0<Hθ(E|Y)=Hθ(X|Y)<1.Source: §8.3 · pp. 37, 39

9 Finite-Block Numerical Illustrations and Gallager Benchmark

The finite-block illustrations show that correction ordering can reverse with the generalized-Gaussian shape parameter, while posterior-envelope and mixture orders achieve zero regret on the displayed finite parameter set. The channel-averaged study compares matched and tilt-containing envelope orders at finite blocklength and relates their estimates to the Gallager benchmark.

9 Finite-Block Numerical Illustrations and Gallager Benchmark

  • The eA and eB correction costs cross near β = 1.257, reversing their relative order between β = 1 and β = 2.For the displayed received magnitudes, c1(eA) < c1(eB), whereas c2(eA) > c2(eB).Source: §9 · p. 40
  • For the displayed blocks and Θf, the posterior-envelope and equal-weight mixture orders have zero regret, while each fixed plug-in order has positive regret.The comparison uses 15 generalized-Gaussian parameter pairs and enumerated correction patterns at blocklengths 4, 8, 12, and 16; it does not establish an approximation result for the continuous parameter family.Source: §9 · p. 40
  • At θ0 = (1.5, 1), the auxiliary family Vtc contains the full conditional power-tilt path for ρ ∈ [0, 1].The finite-block illustration compares this tilt-containing envelope order with the matched posterior order; their conditional mean-rank and ensemble-error quantities differ at finite blocklength.Source: §9 · p. 41, Figure 2 · p. 42

9.1 Channel-averaged finite-block error estimates and Gallager benchmark

  • The matched Gallager benchmark is EU_r(1/4) = 0.14448327 bits/use at ρ⋆ ≈ 0.99882; the reported finite-block values do not establish blocklength monotonicity.Under the full hypotheses of Theorem 13, the corresponding asymptotic exponent equality holds.Source: §9.1 · pp. 41, 43
  • The effective-exponent intervals quantify Monte Carlo uncertainty in the channel-output expectation only, not quadrature or scale-optimization error.They are nominal Student-t intervals for a bounded, potentially skewed conditional-error variable, not exact finite-sample 95% coverage intervals.Source: §9.1 · p. 43

10 Conclusion

The conclusion separates pointwise finite-block minimax regret from the rank-distribution control needed for uniform-subset error exponents. It gives conditions under which an auxiliary posterior-envelope order preserves the matched spectrum and attains the matched exponent, equal to Gallager’s uniform-input random-coding exponent.

10 Conclusion

  • The posterior-envelope order minimizes worst-case posterior-normalized rank regret pointwise, but this alone does not determine the uniform-subset ensemble-average error exponent.That exponent depends on the realized correction-rank distribution, including its right tail, through collisions with nontransmitted codewords.Source: §10 · p. 43
  • For a fixed memoryless channel under uniform input, a 1-tilt-closed decoder posterior family with subexponential conditional Shtarkov complexity preserves the matched rank-moment spectrum on [0, 1].The complexity condition applies on observation sets whose complement probabilities decay exponentially faster than the reciprocal correction-space cardinality.Source: §10 · p. 43
  • With continuous differentiability on [0, 1 + ε] and 0 < Hθ(E|R) < 1, the auxiliary order attains the matched ensemble-average error exponent for every fixed 0 < Rc < 1.The stated result assumes code sizes satisfying loga Mn = nRc + o(n); the exponent equals Gallager’s uniform-input random-coding exponent.Source: §10 · p. 43
  • For generalized-Gaussian BPSK, changing scale at fixed shape leaves correction order unchanged, while changing shape can reverse two corrections’ relative order.Conditional power tilting preserves shape and changes only scale; the decoder posterior family may include auxiliary posteriors not induced by the prescribed channel class.Source: §10 · p. 44
Loading 2609.29688v1…