# Expected number of times random substring occurs inside of larger random string

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?

-

## 1 Answer

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\;.$$

-
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