Skip to content
DraconiticResearch
Search Sources API
186,086 studies31 sourcesUpdated 21 min ago
PreprintCC BY 4.0arXiv

Learning Finite-Memory Binary Sources

  • Maciej Skorski
Open at sourcePDFDOICite

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 ε, and establish *sharp* sample complexity bounds: relative accuracy γ with confidence 1−δ needs γ−2 (1/2−ε)−d (log d+log1/δ) 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 sliding-window (de Bruijn) chain, which stay of order 1/π(w) uniformly in d exactly when ε<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: 106 bits cannot resolve all transitions of an $8$-bit model to better than about 4.5% relative error.

Related

  1. Maximal Center of Distances of Finite Ultrametric Spaces and Perfect Binary Trees
    Oleksiy Dovgoshey, Navjay Singh Jaiswal, Surinder Pal Singh Kainth +2
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  2. Simple finite-dimensional binary Lie superalgebras
    Hani Abdelwahab, Ivan Kaygorodov
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Transferred L∞-structures and a classification of binary brackets for finite-dimensional skew-gentle algebras
    Zixu Li, Liyu Liu, Lingchao Meng
    arXivPreprintCC0Full textAlgebra & number theoryarXiv
  4. Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation
    Jianguo Zhao, Cheuk Ting Li
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Effective Dissipation and Asymptotic Stability in a Finite-Level Quantum System with Wave-Induced Memory
    Thierry Goudon
    HALPreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsHALarXiv

Cite

BibTeXRIS
BibTeX
@misc{skorski2026learning,
  title = {{Learning Finite-Memory Binary Sources}},
  author = {Maciej Skorski},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40845},
  eprint = {2610.40845},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40845},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Learning Finite-Memory Binary Sources
AU  - Maciej Skorski
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40845
UR  - https://arxiv.org/abs/2610.40845
AB  - 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 (1/2−ε)^−d (log d+log1/δ) 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 sliding-window (de Bruijn) chain, which stay of order 1/π(w) uniformly in d exactly when ε<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.
ER  -