{"id":"arxiv/2610.40845","url":"https://arxiv.org/abs/2610.40845","tags":["cs.IT","math.PR"],"score":0,"title":"Learning Finite-Memory Binary Sources","domain":"cs.IT","source":"arxiv","authors":["Maciej Skorski"],"reviews":0,"subject":"cs.IT","summary":"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 $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\\,(\\tfrac12-ε)^{-d}\\,(\\log d+\\log\\tfrac1δ)$ samples up to constants depending on $ε$, 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}