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

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.