arXiv preprint ·
Beyond Typical Strings: Sampling the Complexity Landscape
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
On the Communication-Sensing Tradeoff in DMT-Optimal Space-time-Coded ISAC Systems
Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes
Researcher-in-the-Loop Evolutionary Discovery of Entanglement-Assisted Quantum Code Families
Cyclotomic polynomials with trinomial irreducible factors over finite fields
POST-MIMO: Partition-Oriented Semantic Transmission for MIMO Point Cloud Delivery
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.