Consider the i.i.d. sequence $X_1, X_2, X_3, X_4, X_5, X_6$ where each $X_i$ is one of the four symbols $\{a, t, g, c\}$. Further suppose that $\mathbb{P}(X_1 = a) = 0.1,\ \mathbb{P}(X_1 = t) = 0.2,\ P(X_1 = g) = 0.3$ and $\mathbb{P}(X_1 = c) = 0.4$. Let $Z$ denote the random variable that counts the number of times that the subsequence $cat$ occurs (i.e. the letters $c$, $a$ and $t$ occur consecutively and in the correct order) in the above sequence. Find $\mathbb{E}(Z)$.

• What did you try? Where are you stuck? Please complete your question with such information. (And the answer is 0.032.) – Did Jul 16 '12 at 11:16
• @did:I could not understand how to start and "cat" words is quite cofusing – Argha Jul 16 '12 at 11:20
• Which similar, simpler, problems can you solve? For example, what is the mean number of times a appears in the very same sequence? – Did Jul 16 '12 at 11:23
• Are your probabilities $\mathbb{P}(X_i = a) = 0.1$ and similar? That is, the probability applies to all six positions? – Ross Millikan Jul 16 '12 at 13:26
• Too late...  – Did Jul 16 '12 at 13:28

The solution that uses the linearity of expectation is slick and general. The following is a lower level approach that would get unpleasant in "larger" situations.

Let $W$ be the number of occurrences of the word 'cat.' We have $W=0$, $W=1$, or $W=2$. Then by the definition of expectation, $$E(W)=(0)\Pr(W=0)+(1)\Pr(W=1)+(2)\Pr(W=2).\tag{1}$$ We find the various probabilities. Of course, if we find $\Pr(W=1)$ and $\Pr(W=2)$, then finding $\Pr(W=0)$ will be easy. And anyway we don't even need $\Pr(W=0)$, since in Formula $(1)$ it gets multiplied by $0$. The probability that $W=2$ is $(0.4)(0.1)(0.2)(0.4)(0.1)(0.2)$.

The probability that $W=1$ is trickier. The probability that we have 'cat' in positions $1$, $2$, and $3$ is $(0.4)(0.1)(0.2)$. The same is true for positions $2$, $3$, and $4$, also $3$, $4$, and $5$, also $4$, $5$, and $6$. Add these probabilities. We get $(4)((0.4)(0.1)(0.2)$. However, this counts twice the probability of 'catcat' and we want to count it zero times. So the probability that $W=1$ is equal to $1$ is $$4(0.4)(0.1)(0.2)-2(0.4)(0.1)(0.2)(0.4)(0.1)(0.2).$$ Now calculate, using Formula $(1)$. Observe the cancellation, which tells us that we are probably missing a better and simpler solution, as indeed we are.

To form cat you need c followed by a , followed by t. The probability of getting that exact sequence is p=0.4* 0.1*0.2 But with six random variables there are several distinct ways this can happen namely 1) X1, X2 and X3 2) X2, X3 and X4, 3) X3, X4 and X5 and 4) X4, X5 and X6. So there are 4 distinct ways that three consecutive variables can spell cat in order. Hence you multiply p by 4.

Just a follow up to Wonder's answer: if you want to compute all the probabilities then you can proceed as follows.

The only possibilities are $Z = 0$, $Z = 1$ or $Z = 2$.

Starting with $Z=2$, this will only happen if you get "cat" twice; thus,

\begin{equation} P(Z=2) = P(X_1=c)P(X_2=a)P(X_3=t)P(X_4=c)P(X_2=a)P(X_3=t) = p^2, \end{equation}

where

\begin{equation} p = P(X_1=c)P(X_2=a)P(X_3=t) = 0.4\times0.1\times0.2 = 0.008 \end{equation}

For $Z=1$ we have 4 possibilities (as the $Z_i$ in Wonder's answer), but we must exclude the possibility of having 2 cats in a row. So

\begin{equation} P(Z=1) = 2p + 2p(1-p) = 4p - 2p^2 \end{equation}

Finally,

\begin{equation} P(Z=0) = 1-P(Z=1)-P(Z=2) \end{equation}

The following 3 lines of code instantaneously simulate this in Mathematica, in case you are interested.

n=100000;
data = Map[StringJoin,RandomChoice[{0.1, 0.2, 0.3, 0.4} ->
{"a", "t", "g","c"}, {n,6}]];
z = Map[Length@StringCases[#, "cat"] &, data];


Then either use Histogram[z] to see a plot or (1.0/n)Map[Count[z, #] &, {0, 1, 2}] to get the probabilities themselves.

Let $Z_i$ be a variable that is $1$ if the string $X_{i-1}X_{i}X_{i+1}$ is $cat$, and $0$ otherwise.

Now $Z = Z_2+Z_3+Z_4+Z_5$.

Take expectations on both sides, use linearity of expectations, and note that each of these four $Z_i$'s is 0.4*0.1*0.2.

• Yes, and there was also one more typo ($Z_i$ should be 1 if the condition is met). Thanks vanguard2k for fixing. – Wonder Jul 16 '12 at 14:09