4

A biased coin is tossed $n$ times and heads shows up with probability $p$ on each toss. Let us call a sequence of throws which result in the same outcomes a run, so that for example, the sequence HHTHTTH contains five runs.

If $R$ is a r.v. representing the number of runs then $\mathbb{E}(R) = 1+(n-1)2pq$.

I want to work out the variance $var(R)$.

To do this I would like to use that $var(R) = var(R-1) = \mathbb{E}(R-1)^2 - (\mathbb{E}(R-1))^2$.

Let $I_j$ be the indicator function of the event that the outcome of the $(j+1)$th toss is different from the outcome of the $j$th toss. $I_j$ and $I_k$ are independent if $|j-k| > 1$, so that

\begin{equation*} \begin{aligned} \mathbb{E}(R-1)^2 ={} & \mathbb{E}\left\{\left(\sum_{j=1}^{n-1}I_j\right)^2\right\} \\ = {} &\mathbb{E} \left(\sum_{j=1}^{n-1} I_{j}^{2}+2 \sum_{j=1}^{n-2} I_{j} I_{j+1}+2 \sum_{j=1}^{n-3} \sum_{k=j+2}^{n-1} I_{j} I_{k}\right). \end{aligned} \end{equation*}

Now $\mathbb{E}(\sum_{j=1}^{n-1} I_{j}^{2}) = (n-1)2pq$ and $\mathbb{E}(2 \sum_{j=1}^{n-2} I_{j} I_{j+1}) = (n-2)2pq$.

We also have that $\mathbb{E}(2 \sum_{j=1}^{n-3} \sum_{k=j+2}^{n-1} I_{j} I_{k}) = (n-3)(n-4)(2pq)^2$ I believe.

But now I have lost confidence and I am not sure how to get the final result for the variance.

Is my approach correct and what should it be in the end?

gaussplustwo
  • 43

2 Answers2

4

Yes! Your approach is correct, and the calculations also arrived at correct results [edit: save in the last expectation, where the result should have been $(n-2)(n-3)(2pq)^2$].

Now, the only thing that remains to be done is to plug in the (partial) results to arrive at an expression for the variance.

That is: \begin{align*} \text{Var}(R) &= \text{Var}(R-1) \\ &= \mathbb{E}[(R-1)^2]-(\mathbb{E}[R-1])^2 \\ &= \mathbb{E} \left[\sum_{j=1}^{n-1} I_{j}^{2}\right] + \mathbb{E} \left[2 \sum_{j=1}^{n-2} I_{j} I_{j+1}\right] + \mathbb{E} \left[2 \sum_{j=1}^{n-3} \sum_{k=j+2}^{n-1} I_{j} I_{k}\right] - \left(\mathbb{E} \left[\sum_{j=1}^{n-1}I_j\right]\right)^2 \\ &= (n-1)2pq + (n-2)2pq +(n-2)(n-3)(2pq)^2-((n-1)2pq)^2 \\ &= 2pq(2n-3)+(2pq)^2(-3n+5) \end{align*}

Nicolas Agote
  • 1,213
  • Thank you so much! – gaussplustwo Oct 05 '22 at 14:15
  • 1
    Following @ParclyTaxel 's hint about the origin of the question I found an answer online of $2pq(2n-3-2pq(3n-5))$ . This doesn't look the same though, – gaussplustwo Oct 05 '22 at 14:59
  • 1
    Ah, iit looks like $(n-3)(n-4)$ should be $(n-2)(n-3)$ but I am not sure why yet. – gaussplustwo Oct 05 '22 at 15:27
  • 1
    You're right; one way to convince oneself of the fact is to see that for $j=n-3=(n-2)-1$ there is only $1$ possible $k$, for $j=(n-2)-2$ there are $2$ possible $k$... and for $j=(n-2)-(n-3)=1$ there are $n-3$ possible $k$. Then the total ammount of terms in that sum is $\sum_{l=1}^{n-3}l=\frac{(n-3)(n-3+1)}{2}$ and what you said can be deduced from that. Sorry for the oversight, and thanks for letting me know. I'll edit the answer so as to account for this. – Nicolas Agote Oct 05 '22 at 15:45
  • Thank you again. – gaussplustwo Oct 05 '22 at 15:51
3

You got this problem in Grimmett & Stirzaker. Let $m=n-1$ be the number of indicator variables we work with and $x=2pq$, then the expectations of binomials of indicator variables in the expansion of $E\left(\left(\sum_jI_j\right)^2\right)$ should group as follows:

  • $m$ terms of $E(I_1^2)=E(I_1)=x$
  • $2(m-1)$ terms of $E(I_1I_2)=pqp+qpq=x/2$
  • $(m-2)(m-1)$ terms of $E(I_1)^2=x^2$

Note that $m+2(m-1)+(m-2)(m-1)=m^2$. Then $$E((R-1)^2)=mx+(m-1)x+(m-2)(m-1)x^2$$ $$\operatorname{Var}(R)=E((R-1)^2)-E(R-1)^2=mx+(m-1)x+(m-2)(m-1)x^2-(mx)^2=x(2(m+x)-3mx-1)$$

Parcly Taxel
  • 103,344