Expectation Bernoulli Trials

Question

A run is a maximal sequence of success in a sequence of Bernoulli trials. For example, in the sequence $S,S,S,F,S,S,F,F,S$ where $S$ is success and $F$ is failure there are three runs consisting of three successes, two successes and one success. Let $R$ denote the random variable on the set of sequence of $n$ independent bernoulli trials that counts the number of runs in the sequence. Find $\operatorname{E}[R]$.

[Hint: Show that $R$ is a summation of $I_j$ where $j$ goes form $1$ to $n$ and $I_j = 1$ if a run begins at the $j\text{th}$ Bernoulli trial and $0$ otherwise. Find $\operatorname{E}(I_1)$ and then $\operatorname{E}(I_j)$].

Answer 1

It's trivial that $R = I_1 + I_2 + \cdots + I_n$, why? because a sequence with $R$ runs must have $R$ positions where each run starts, if there are 3 runs, there must exist 3 positions in the sequence where each of them starts. For example the runs at S,S,S,F,S,S,F,F,S start at positions 1,5, and 8, meaning $I_1 = I_5 = I_8 = 1$, the rest of the $I_j$'s are zero. Obviously $P(R=n) = 0$ because for there to exist at least 2 runs, there must be failures in between, which means at least one $I_j = 0$. Now you can calculate the expectation of $R$ $$ E(R) = E(I_1 + I_2 + \cdots + I_n) = E(I_1) + E(I_2) + \cdots + E(I_n) $$ The problem has been reduced to finding the expected value of each $I_j$ and summing over all of them. You have two cases:

• $P(I_1=1) = p$, where $p$ is the probability of success of the Bernoulli trials, and
• $P(I_j=1) = (1-p)p$ where $j \neq 1$, because if $j$ is not the first position, there must exist a failure in the previous position $(1-p)$, and a success at position j $(p)$. Therefore \begin{align*} E(R) & = E(I_1 + I_2 + \cdots + I_n)\\ & = E(I_1) + E(I_2) + \cdots + E(I_n)\\ & = p + (1-p)p + \cdots + (1-p)p\\ & = p + (n-1)(1-p)p \end{align*} For example, if $n = 3$ and $p = 0.5$ you have $8$ possible outcomes with equal probability each: $$ FFF \to 0 \text{ runs}\\ FFS \to 1 \text{ runs}\\ FSF \to 1 \text{ runs}\\ FSS \to 1 \text{ runs}\\ SFF \to 1 \text{ runs}\\ SFS \to 2 \text{ runs}\\ SSF \to 1 \text{ runs}\\ SSS \to 1 \text{ runs} $$ Therefore the expected number of runs is: $$ \frac{(0+1+1+1+1+2+1+1)}{8} = \frac{8}{8} = 1$$ Using the previous formula yields the same result (but quicker): $$ \operatorname{E}(R) = p + (n-1)(1-p)p = 0.5 + (3-1)\times 0.5 \times 0.5 = 1$$