Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have two random strings over an $N$-letter alphabet: one is a shorter $M$-letter string, and one is a longer $L$-letter string. Assuming that two or more instances of the shorter string can overlap, what is the probability, in general, that the $M$-letter string appears $k$ times in the $L$-letter string?

To clarify the comment about overlapping short strings, consider two strings over a binary alphabet: a longer string "000000", and a shorter string "00000". Here we would say that there are two overlapping instances of the short string in the longer string, with a four-character overlap.

share|cite|improve this question
It depends on how they can overlap: $0000$ is more likely to appear $0$ times or $L-3$ times than is $0101$, and less likely to appear an "average" number of times. – Henry Jun 20 '12 at 21:25
I think it depends partly on what the shorter string actually is, not just on its length. The expected number of 0000s in a long random string should be higher than the expected number of 0111s, because an appearance of 0111 at position $k$ excludes it from appearing at any of positions $k+1$ through $k+3$, whereas an appearance of 0000 at position $k$ does not exclude it from appearing anywhere else. – MJD Jun 21 '12 at 3:15
@Mark The distributions are different but the expected numbers are the same. – Did Jun 21 '12 at 6:16
@did Is there an easy way to see that? – MJD Jun 21 '12 at 13:31
@Mark: Yes: the expected number of times the word $w$ appears is the sum over the positions $i$ of the probability $p(w,i)$ that $w$ appears beginning at $i$. The sequence is stationary hence $p(w,i)=p(w)$ does not depend on $i$. The letters are i.i.d. and uniform hence $p(w)=N^{-|w|}$ where $|w|$ is the length of $w$. QED. (Remember: the expectation of a sum is the sum of the expectations, even for dependent random variables.) – Did Jun 21 '12 at 16:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.