Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2004-11-29
J. Stat. Phys. 126 (2007) 207-242
Physics
Condensed Matter
Statistical Mechanics
44 pages and 8 figures. Major revision of previous version. The lattice gas analogy has been worked out in full, including vir
Scientific paper
10.1007/s10955-006-9247-z
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) $k \gg r^l \gg 1$ (Gaussian) and $k,l \to \infty$ such that $k/r^l$ is finite (Compound Poisson). However, it is known that these distributions do now work well in the intermediate regime $k \gtrsim r^l \gtrsim 1$. 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.
Mungan Muhittin
No associations
LandOfFree
String Matching and 1d Lattice Gases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with String Matching and 1d Lattice Gases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and String Matching and 1d Lattice Gases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-449216