Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a four-letter alphabet containing A, B, C, and D. What is the expected number of times a string of length $m$ occurs inside of larger random substring of length $n$, both generated from the same alphabet? I think I've got it so far for an even distribution, where each letter has a probability of $0.25$:

$$(n-m)\cdot\left(\frac 1 4\right)^m$$

What if the letters are not evenly distributed? What if A and B had probabilities of $0.115$, and C and D had probabilities of $0.385$? How does that change the problem?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

You miscounted by $1$: A string of length $m$ fits into a string of length $n$ once, not $0$ times, so it should be $(n-m+1)$.

The problem is essentially the same if the probabilities differ. By linearity of expectation, you still only have to take $n-m+1$ times the probability for a single match. If you have $k$ letters $a_1$ through $a_k$ that occur with probabilities $p_1$ through $p_k$, the expected number of matches is

$$ (n-m+1)\left(\sum_{i=1}^kp_i^2\right)^m\;. $$

share|improve this answer
Could you please explain this is little more detail. I am sorry but I just am not able to get it in my head. What I was doing is expected counts = summation (count * probability) . I am not able to reach to the formula you mentioned with it. –  Naman Aug 8 at 19:51
@Naman: Do you understand linearity of expectation? Did you check out the link? –  joriki Aug 8 at 20:25
@jorki Yes I did check and I understand that. I am reading book (books.google.com/…) page 223 for same explanation. But unable to understand properly. –  Naman Aug 8 at 20:26
@Naman: It seems that that book treats "cyclic strings"? That's why they have $m$ (our $n$) where we have $n-m+1$, because we're not allowing the substring to wrap around the string cyclically. (In case this doesn't resolve your problem, please be a lot more specific on what your problem is.) –  joriki Aug 8 at 20:34
I could understand that part. It should be (n-m+1) but not able to get the probability part. Shouldn't it be prod(probability of each alphabet in given substring) ? I am not able to understand the second part of your formula. Why is it summing over squared probability over alphabets? –  Naman Aug 8 at 20:36

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.