Learning Finite-Memory Binary Sources

arXiv:2610.40845v1 Announce Type: new Abstract: Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $\epsilon$, and establish *sharp* sample complexity bounds: relative accuracy $\gamma$ with confidence $1-\delta$ needs $\gamma^{-2}\,(\tfrac12-\epsilon)^{-d}\,(\log d+\log\tfrac1\delta)$ samples up to constants depending on $\epsilon$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/\pi(w)$ uniformly in $d$ exactly when $\epsilon