String matching and 1d lattice gases

DOI10.1007/S10955-006-9247-ZzbMATH Open1115.82007arXivcond-mat/0411706OpenAlexW2079374891MaRDI QIDQ878347FDOQ878347

Authors: Muhittin Mungan 

Publication date: 26 April 2007

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: We calculate the probability distributions for the number of occurrences $n$ of a given $l$ letter word in a random string of $k$ letters. Analytical expressions for the distribution are known for the asymptotic regimes (i) $kgg{r}^{l}gg1$ (Gaussian) and $k,loinfty$ such that $k/r^l$ is finite (Compound Poisson). However, it is known that these distributions do now work well in the intermediate regime $kgtrsim{r}^{l}gtrsim1$. We show that the problem of calculating the string matching probability can be cast into a determining the configurational partition function of a 1d lattice gas with interacting particles so that the matching probability becomes the grand-partition sum of the lattice gas, with the number of particles corresponding to the number of matches. We perform a virial expansion of the effective equation of state and obtain the probability distribution. Our result reproduces the behavior of the distribution in all regimes. We are also able to show analytically how the limiting distributions arise. Our analysis builds on the fact that the effective interactions between the particles consist of a relatively strong core of size $l$, the word length, followed by a weak, exponentially decaying tail. We find that the asymptotic regimes correspond to the case where the tail of the interactions can be neglected, while in the intermediate regime they need to be kept in the analysis. Our results are readily generalized to the case where the random strings are generated by more complicated stochastic processes such as a non-uniform letter probability distribution or Markov chains. We show that in these cases the tails of the effective interactions can be made even more dominant rendering thus the asymptotic approximations less accurate in such a regime.

Full work available at URL: https://arxiv.org/abs/cond-mat/0411706

Recommendations

• scientific article; zbMATH DE number 840348
• The statistics of words on rings
• Exact distribution of word occurrences in a random sequence of letters
• A probabilistic analysis of a pattern matching problem
• Distribution of the number of words with a prescribed frequency and tests of randomness

zbMATH Keywords

combinatoricstheory of liquidslattice gasesPattern occurrences

Mathematics Subject Classification ID

Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Title not available (Why is that?)
• A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials
• A unified approach to word occurrence probabilities
• A fast string searching algorithm
• Fast Pattern Matching in Strings
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Title not available (Why is that?)
• Compound Poisson approximation of word counts in DNA sequences
• Compound Poisson approximations for word patterns under Markovian hypotheses
• String overlaps, pattern matching, and nontransitive games
• Exact distribution of the distances between any occurrences of a set of words
• Exact distribution of word occurrences in a random sequence of letters
• Title not available (Why is that?)
• Periods in strings
• Combinatorics of periods in strings.
• On pattern frequency occurrences in a Markovian sequence
• Maximal Prefix-Synchronized Codes
• The Occurrence of Sequence Patterns in Repeated Dependent Experiments
• On pattern occurrences in a random text
• A limit theorem for the number of non-overlapping occurrences of a pattern in a sequence of independent trials
• Endliche 0-1-Folgen mit gleichen Teilblöcken.
• A Quantitative Theory of Genetic Recombination and Chiasma Formation

Cited In (1)

• Content-based networks: A pedagogical overview

This page was built for publication: String matching and 1d lattice gases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q878347)