# Moments on number of occurrences of substring

Let $S$ be a string of length $n$. Each character of $S$ has probability $p$ of being 'A' and probability $1-p=q$ of being 'B'. $R$ is the number of occurrences of the substring 'AB' in $S$. I'd like to determine $\mathbf{E}[R]$ and $\mathbf{var}[R]$ . I can determine the expectation via a recursive definition and total expectation:

$\mathbf{E}[R] = pq\left(1+\mathbf{E}\left[R_{n-1}\right]\right)+\left(1-pq\right)\mathbf{E}\left[R_{n-1}\right]$

But I am not sure how I can approach the problem for determining the variance.

I tried defining a Probability Mass Function but it looks like it will get messy very soon. $\Pr(R=x) = \binom{n-x}{x}\cdot\left(pq\right)^{x} \cdot \text{probability of no other ABs}$

And that "no other" probability ends up being, for example for $x=1$:

$\sum_{i=0}^{u}p^i q^{u-1} \cdot \sum_{i=0}^{v}p^i q^{u-1}$ summed over all $u+v+2=n$ but I think there might be a better way.

-
Isn't this more or less equivalent to this very recent question: math.stackexchange.com/questions/6008/… ? – Hans Lundmark Oct 4 '10 at 18:30
Thank you for the reference and terminology. – Gus Oct 4 '10 at 20:01

I presume all the characters are independent.

Let $X_1,\ldots,X_{n-1}$ be the random variables defined as follows: $X_i=1$ if there is $AB$ starting at the $i$-th position, otherwise $X_i=0$. Then $R=X_1+\cdots+X_{n-1}$. By linearity of expectation $E(R)=\sum_i E(X_i)$ and $E(R^2)=\sum_{i,j} E(X_i X_j)$. Now $E(X_i)=pq$ so $E(R)=(n-1)pq$. IF $i=j$ then $X_i X_j=X_i^2=X_i$; if $|i-j|=1$ then $X_i X_j=0$ and if $|i-j|\ge2$ then $X_i$ and $X_j$ are independent so that $E(X_i X_j)=E(X_i)^2 =p^2 q^2$. Now it's just book-keeping to find $E(R^2)$ and so also $Var(R)$.

-
To find $E[R^2]$, I sum: \mathbf{E}\left[R_{n}^{2}\right]=\sum_{i=1}^{n}\left(\sum_{i=j}^{n}\mathbf{E}\le‌​ft[X_{i}X_{j}\right]\right) and split the sum: \sum_{i=1}^{n}\mathbf{E}\left[X_{i}X_{i}\right]+2\sum_{i=1}^{n-1}\mathbf{E}\left‌​[X_{i}X_{i+1}\right]+2\sum_{i=3}^{n}\sum_{j=1}^{i-2}\mathbf{E}\left[X_{i}X_{j}\ri‌​ght] – Gus Oct 5 '10 at 0:14
darn, jsMath doesn't render the comments. – Gus Oct 5 '10 at 0:16