Paper 2026/2417

Unpredictability from Parity: Understanding Linear Correctors for Markovian Sources

Abstract

Linear correctors reduce the bias of random bits via parity (XOR), but their guarantees are known mostly for independent bits, an assumption violated by many physical entropy sources. We give a general, exact formula for the parity bias of dependent bits from a (hidden, possibly non-homogeneous) Markov chain, as a product of twisted transfer kernels. Under next-bit unpredictability, i.e. conditional bias at most $\beta$, the decay is governed by $\beta$ itself: sharp for a one-bit context, $|\mathrm{bias}|\le\beta^{\lceil n/2\rceil}$, and \emph{near-optimal} for an $m$-bit context, within a factor $3^{1/3}\approx1.44$ of the best possible per-bit rate, which is at least $\beta^{1/(m+1)}$ (attained by a noisy LFSR) and asymptotically equal to it as $\beta\to0$. Against the best previous bound (Zhou and Bruck, ISIT 2011) we \emph{correct the exponent} and \emph{tighten the bound on $n$ bits by a factor of about $2^{\lfloor(n-1)/2\rfloor}/\beta$}, with a matching construction. The decay is non-monotone, so a corrector should be certified at every operating length, or via the envelope $\beta^{\lceil n/2\rceil}$. Finally, bounded memory is necessary: if unpredictability is imposed on the full history, XOR-ing does not reduce the bias at all.