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.

  • 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
  • 1
    @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
  • 2
    @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 clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.