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.

  • $\begingroup$ 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. $\endgroup$ – Henry Jun 20 '12 at 21:25
  • $\begingroup$ 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. $\endgroup$ – MJD Jun 21 '12 at 3:15
  • 1
    $\begingroup$ @Mark The distributions are different but the expected numbers are the same. $\endgroup$ – Did Jun 21 '12 at 6:16
  • $\begingroup$ @did Is there an easy way to see that? $\endgroup$ – MJD Jun 21 '12 at 13:31
  • 2
    $\begingroup$ @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.) $\endgroup$ – Did Jun 21 '12 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.