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.

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|improve this question
2  
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
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.