Let $X$ denote the number of instances in which a head is followed by a tail. Find variance of $X$.

Question

Suppose $n (n\ge 2)$ coins are tossed independently in a row. Let $X$ denote the number of instances in which a head is followed by a tail. Find variance of $X$.

I tried using indicator random variables.

Let $Y_n$ be the event of the $n^{th}$ toss being a head and the $n+1^{th}$ toss being a tail. $P(Y_n)=\displaystyle\frac{1}{4} \forall n$. Let $I_n$ be the indicator $\text{R.V.}$ for $Y_n$.

I found $E(X)=\displaystyle\frac{(n-1)}{4}$

I'm struggling with $E(X^2)$. The entire calculation becomes too messy and doesn't seem right. I'm getting a quadratic equation of $n$, which is definitely heading in the wrong direction.

Can someone please guide me with this problem? Thank you.

Answer 1

For $ n \ge 2$, let $ {\left({X}_{i}\right)}_{1 \leqslant i \leqslant n}$ be i.i.d random variables and $ f \colon {\mathbb{R}}^{2} \rightarrow \mathbb{R}$ be any bounded measurable function, finally, let

\begin{equation}X = \sum _{i = 1}^{n-1} f \left({X}_{i} , {X}_{i+1}\right)\end{equation}

Then

\begin{equation}\text{Var} \left(X\right) = \left(n-1\right) {\nu}+2 \left(n-2\right) \left({\xi}-{{\mu}}^{2}\right)\end{equation}

where

\begin{equation}{\mu} = E \left[f \left({X}_{1} , {X}_{2}\right)\right], \quad {\nu} = \text{Var} \left(f \left({X}_{1} , {X}_{2}\right)\right), \quad {\xi} = E \left[f \left({X}_{1} , {X}_{2}\right) f \left({X}_{2} , {X}_{3}\right)\right] \left[n \geqslant 3\right]\end{equation}

Indeed, it is clear that $E \left(X\right) = \left(n-1\right) {\mu}$ and

\begin{equation}\begin{array}{rcl}E \left[{X}^{2}\right]&=&\displaystyle \sum _{i = 0}^{n-1} \sum _{j = 0}^{n-1} E \left[f \left({X}_{i} , {X}_{i+1}\right) f \left({X}_{j} , {X}_{j+1}\right)\right]\\ &=&\displaystyle \sum \sum _{\left|i-j\right| = 0}+\sum \sum _{\left|i-j\right| = 1}+\sum \sum _{\left|i-j\right| \geqslant 2}\\ &=&\left(n-1\right) \left({\nu}+{{\mu}}^{2}\right)+2 \left(n-2\right) {\xi}+\left({\left(n-1\right)}^{2}-\left(n-1\right)-2 \left(n-2\right)\right) {{\mu}}^{2}\\ &=&\left(n-1\right) {\nu}+2 \left(n-2\right) {\xi}+{\left(E \left[X\right]\right)}^{2}-2 \left(n-2\right) {{\mu}}^{2} \end{array}\end{equation}

which implies the result.

In our case, we have $ f \left({X}_{i} , {X}_{i+1}\right) = 1$ if $ \left({X}_{i} , {X}_{i+1}\right) = \left(0 , 1\right)$ and $0$ otherwise, where $ {X}_{i} = 1$ if the $ i$ -th coin is a tail and $0$ otherwise. It follows that

\begin{equation} {\mu} = \frac{1}{4} \qquad {\nu} = \frac{3}{16} \qquad {\xi} = 0\end{equation}

Hence

\begin{equation}\text{Var} \left(X\right) = \frac{3 \left(n-1\right)}{16}-\frac{2 \left(n-2\right)}{16} = \frac{n+1}{16}\end{equation}

Answer 2

\begin{align} E[X^2] &= E[(I_1+\dots+I_{n-1})^2] \\&= E\left[\sum_{k=1}^{n-1}\sum_{\ell=1}^{n-1}I_kI_\ell\right] \\&= \sum_{k=1}^{n-1}\sum_{\ell=1}^{n-1}E\left[I_kI_\ell\right] \\&= \sum_{k=1}^{n-1}\sum_{\ell=1}^{n-1}P(Y_k\cap Y_\ell) \end{align} You just need to figure out how to evaluate $P(Y_k\cap Y_\ell)$, for each $k,\ell\in \{1,\dots,n-1\}$. There are several cases to consider.

1. If $k=\ell$, then $P(Y_k\cap Y_\ell)=P(Y_k)=1/4$.

2. If $k=\ell+1$, then $P(Y_k\cap Y_\ell)=0$, because $Y_k$ requires a tails at position $k+1$, but $Y_{k+1}$ requires a heads at position $k+1$. The same is true when $k=\ell-1$.

3. In all other cases, the events $Y_k$ and $Y_\ell$ involve disjoint sets of coins, so the events are independent, and $P(Y_k\cap Y_\ell)=P(Y_k)P(Y_\ell)=(1/4)(1/4)=1/16$.

In the summation $\sum_{k=1}^{n-1}\sum_{\ell=1}^{n-1}P(Y_k\cap Y_\ell)$, there are $n-1$ terms corresponding to case $1$, there are $2(n-2)$ terms corresponding to case $2$, while the remaining $(n-1)^2-(n-1)-2(n-2)$ terms fall in case $3$. Therefore,

$$ E[X^2]=(n-1)\cdot \frac14+[(n-1)^2-(n-1)-2(n-2)]\cdot \frac1{16} $$

Finally, you can show that $\text{Var }X=E[X^2]-(E[X])^2$ simplifies to $(n+1)/16$. However, there is no quick explanation which matches the simplicity of this final answer. Sometimes in math, you need to plod your way through a complicated looking summation, it is unavoidable. You should not say "the entire calculation becomes too messy and doesn't seem right," you should accept that some calculations will be messy.

Answer 3

$\displaystyle \begin{array}{{>{\displaystyle}l}} Actually,\ you\ can\ avoid\ calculating\ E\left[ X^{2}\right]\\ \\ Let\ Y_{i} \ be\ the\ event\ of\ the\ i^{th} \ toss\ being\ a\ head\ and\ the\ ( i+1)^{th} \ toss\ being\ a\ tail.\ \\ \ \\ Let\ I_{i} \ be\ the\ indicator\ R.V.\ for\ Y_{i} .\ \\ Let\ p\ =\ Pr( I_{i} \ =\ 1) \ =\ Pr( Y_{i}) =\frac{1}{4} \ ,\ i\ =\ 1,2...n-1.\\ \\ Then,\ Var( I_{i}) \ =p( 1-p) \ =\ \frac{3}{16}\\ \\ We\ can\ write\\ \\ Var( I_{1} +I_{2} \ +\ ...\ I_{n-1}) \ \ =\ \sum _{i=1}^{i=n-1} Var( I_{i}) \ +\ 2\sum \sum _{i< j} Cov( I_{i} ,\ I_{j})\\ Now,\ \\ \\ Cov( I_{i} ,\ I_{j}) \ =\ 0,\ j\neq \ i+1\ ( \ Because\ tosses\ are\ independent)\\ Cov( I_{i} ,\ I_{j}) \ =\ \frac{-1}{16} \ ,\ j=\ i+1\ ( this\ value\ can\ be\ calculated\ easily)\\ \\ \\ Since\ there\ are\ n-2\ consecutive\ I_{i} ,\ I_{i+1} \ pairs,\ we\ have\\ \\ Var( I_{1} +I_{2} \ +\ ...\ I_{n-1}) \ =\ ( n-1)\frac{3}{16} \ +\ 2( n-2)\frac{-1}{16} \ =\ \frac{n+1}{16}\\ \\ \\ \\ \end{array}$