Metraipolis › archive › dc_cd93062d7eb7

Beyond Typical Strings: Sampling the Complexity Landscape — arXiv:2611.00162

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.00162
License (as archived): CC0-1.0
Archived: 2026-11-03T11:38:36.324Z
SHA-256 of the archived text: 57e138d06a8db98d59c5ce8c728114ec60a55ef6351b0a4720406e72a1d16c8f
Stable URL of this page: https://metraipolis.com/documento/dc_cd93062d7eb7

How to cite

Beyond Typical Strings: Sampling the Complexity Landscape — arXiv:2611.00162 — arXiv (en), https://arxiv.org/abs/2611.00162 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd93062d7eb7 (Metraipolis archive dc_cd93062d7eb7, sha256 57e138d06a8db98d59c5ce8c728114ec60a55ef6351b0a4720406e72a1d16c8f)

BibTeX

@misc{dccd93062d7eb7,
  title = {Beyond Typical Strings: Sampling the Complexity Landscape — arXiv:2611.00162},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00162},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd93062d7eb7; sha256 57e138d06a8db98d59c5ce8c728114ec60a55ef6351b0a4720406e72a1d16c8f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00162. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Uniform random sampling of strings is overwhelmingly dominated by high-complexity strings, leaving the much smaller set of low- and intermediate-complexity strings largely unexplored. Here, we adapt the nested neutral set estimator (NNSE), a Monte Carlo rare-event sampling method, to estimate the distribution P(K) of complexity values for binary strings of fixed length. NNSE allows us to explore the full complexity landscape, including exponentially rare low-complexity regions that are inaccessible to direct sampling, for string lengths up to several hundred. We apply the method to several widely used complexity measures: Lempel-Ziv 76 (LZ76), Lempel-Ziv 78 (LZ78), context tree weighting (CTW), the block decomposition method (BDM), and block entropy. We further introduce uniform complexity weighting (UCW), which gives equal weight to different complexity levels rather than to individual strings. This approach provides a dataset-independent framework for comparing complexity measures across their full range and reveals substantial differences between measures for low- and intermediate-complexity strings that are largely hidden by conventional uniform sampling. Using the NNSE to perform UCW sampling allows us to compare complexity measures across their full range in a dataset-independent way. This reveals differences in their behavior for low- and intermediate-complexity strings that are practically inaccessible to conventional uniform sampling.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.00162 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:37.168Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).