Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Isn't this more or less equivalent to this very recent question:… ? – Hans Lundmark Oct 4 '10 at 18:30
Thank you for the reference and terminology. – Gus Oct 4 '10 at 20:01
up vote 4 down vote accepted

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)$.

share|cite|improve this answer
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

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.