String matching and 1d lattice gases

DOI10.1007/S10955-006-9247-ZMaRDI QIDQ878347zbMATH OpenOpenAlexFDO

Authors Muhittin Mungan

Publication date 26 April 2007

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

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

zbMATH Keywords

combinatoricslattice gasesPattern occurrencestheory of liquids

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)