Learning Finite-Memory Binary Sources

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}(\frac{1}{2}-\epsilon {)}^{-d}(\log d+\log \frac{1}{\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 <\frac{3}{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.