March 22, 2006 15:30
Muhittin Mungan, B. Ü.
on Random Strings, The Combinatorics of Matches and 1d Lattice Gases

I consider the probability distribution for the number of occurrences of a given word inside a random string whose letters have been generated by a stationary stochastic process. The problem is non-trivial due to the possibility of overlapping occurrences and has applications in communication theory and analysis of biological sequences. I will show that this problem can be cast into one of determining the partition function of a 1d lattice gas with interacting particles. Using this analogy, the probability distribution can be obtained from a virial expansion.