Guesswork Under Linear Constraints: Exact Exponent for Coset Decoding

Abstract

We establish the exact exponential growth rate of the $\ddot{I}$-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_{\hat{I}}\pm (p)$ is the binary Rényi entropy and $R=k/n$ is the code rate. The exponent shifts down by exactly $\ddot{I}(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(\hat{I}´)$; (ii)~the exact exponent for $L_n$-list (``$k$-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order $\ddot{I}{\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}}(\hat{I}´)$, the guesswork exponent equals $(1+\ddot{I})\ddot{I}{ˆ}_{1/(1+\ddot{I})}(g_{\mathcal{E}})-\ddot{I}\ddot{I}{ˆ}_1(g_{\mathcal{E}})$, where $\ddot{I}{ˆ}_{\hat{I}}\pm (g)={\sup }_{\hat{I}}´[g(\hat{I}´)+\hat{I}\pm \ell (\hat{I}´)]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, $\hat{I}{›}_q(\ddot{I})=\ddot{I}h_{1/(1+\ddot{I})}^{(q)}(P)+\ddot{I}(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.