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<\tfrac3{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.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page