AI summaryⓘ
The authors analyze how hard it is to guess a specific noise pattern when using a random binary linear code, measured by the growth rate of the expected guesswork moments. They find an exact formula that shows how the code's rate and noise distribution affect this difficulty, extending previous results by including constraints from the code's parity checks. They also generalize their findings to other code ensembles and alphabets, providing formulas that depend on the weight distribution of the codes. Simulations confirm their theoretical predictions and they further refine their results by giving precise second-order terms. Their work offers a detailed understanding of guesswork in error-correcting codes under noisy conditions.
guessworkrandom linear codesRényi entropybinary symmetric noisecode rateweight enumeratorfinite-length analysisLDPC codesuniversality theoremlist decoding
Abstract
We establish the exact exponential growth rate of the $ρ$-th moment of the constrained guesswork $G_{\mathrm{coset}}$ -- the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d.\ Bernoulli$(p)$ noise: \( \lim_{n\to\infty} \frac{1}{n}\log_2\Eb\!\left[G_{\mathrm{coset}}^ρ\right] = ρ\,h_{\frac{1}{1+ρ}}(p)\;+\;ρ(R-1), \, ρ>0, \) where $h_α(p)$ is the binary Rényi entropy and $R=k/n$ is the code rate. The exponent shifts down by exactly $ρ(1-R)$ relative to the unconstrained Arıkan--Merhav exponent, with each of the $n(1-R)$ parity checks contributing equally. Finite-length simulations confirm convergence from below. We further establish: (i)~a transfer theorem expressing the partition-function exponent in terms of an arbitrary weight-enumerator growth rate $g(δ)$; (ii)~the exact exponent for $L_n$-list (``$k$-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order $ρ\log_2 n$. Beyond the binary i.i.d.\ setting, we prove a universality theorem: for any code ensemble $\mathcal{E}$ whose weight enumerator concentrates at rate $g_{\mathcal{E}}(δ)$, the guesswork exponent equals $(1+ρ)ψ_{1/(1+ρ)}(g_{\mathcal{E}})-ρ\,ψ_1(g_{\mathcal{E}})$, where $ψ_α(g)=\sup_δ[g(δ)+α\ell(δ)]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, $Λ_q(ρ)=ρ\,h^{(q)}_{1/(1+ρ)}(P)+ρ(R-1)\log_2 q$, and for Gallager's regular LDPC ensemble, obtaining a closed-form guesswork exponent via an exact finite-length identity for the ensemble-average weight enumerator.