Beyond Typical Strings: Sampling the Complexity Landscape
Abstract
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.
Related
- On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
- Typical periodic optimization and freezing phase transition: Dini potentials and beyond
- Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
- Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
- Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
BibTeX
@misc{erturk2026beyond,
title = {{Beyond Typical Strings: Sampling the Complexity Landscape}},
author = {Abdurrahman Hadi Erturk and Joshua Sharkey and Nora S Martin and Kamal Dingle and Ard A Louis},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00162},
eprint = {2611.00162},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00162},
}
RIS
TY - UNPB
TI - Beyond Typical Strings: Sampling the Complexity Landscape
AU - Abdurrahman Hadi Erturk
AU - Joshua Sharkey
AU - Nora S Martin
AU - Kamal Dingle
AU - Ard A Louis
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00162
UR - https://arxiv.org/abs/2611.00162
AB - 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.
ER -