Two "Heads" Are Indeed Better Than One

Relevant wiki: Discrete Random Variables - Indicator Variables

We use the indicator variables as stated by Mark, where $X_i$ is the RV that is equal to 1 if Heads is tossed by both the $j$ and $j+1$ coins, and 0 otherwise. We have $X = \sum X_i$ . We calculate the variance as follows:

$Var (X) = \sum Var (X_i) + 2 \sum_{i < j } Cov(X_i, X_j)$

1. $\sum Var (X_i) = (n-1) Var (X_1) = (n-1) \times \frac{3}{16}$ .
2. For $|i-j| \geq 2$ , the coin tosses are independent and so the covariance is 0.
3. For $|i-j| = 1$ , the covariance is $Cov(X_i, X_{i+1} ) = E[X_i X_{i+1} ] - E[X_i] E[X_{i+1} ] = \frac{1}{8} - \frac{1}{4} \times \frac{1}{4} = \frac{1}{8}$

Hence, $Var (X) = (n-1) \times \frac{3}{16} + 2 (n-2) \times \frac{1}{8} + 0 = \frac{5n-7}{16}$ .

Relevant wiki: Expected Value - Problem Solving

Suppose that I toss a coin $n$ times in a row. For any $1 \le j \le n-1$ , let $X_j$ be the random variable which is equal to $1$ if Heads is tossed by the $j^\mathrm{th}$ and $(j+1)^\mathrm{st}$ coins, and $0$ otherwise, so that the total number of occurrences of consecutive Heads is $X \; = \; X_1 + X_2 + \cdots + X_{n-1} \;.$ It is clear that $E[X_j] \,=\, P[X_j = 1] \; = \; \tfrac14$ for each $1 \le j \le n-1$ , and hence that $N \; = \; E[X] \; = \; E[X_1] + E[X_2] + \cdots + E[X_{n-1}] \; = \; \tfrac14(n-1) \;.$ Now suppose that $1 \le i,j \le n-1$ and consider $E[X_iX_j] = P[X_i=X_j=1]$ . If $i=j$ , this is just the probability that $X_i=1$ , namely the probability of tossing two Heads in a row. If $i$ and $j$ are consecutive, this is the probability of tossing three Heads in a row; otherwise this is the probability that four coins come up Heads. In other words $E[X_iX_j] \; = \; \left\{ \begin{array}{lll} \tfrac14 & \qquad & i=j \\ \tfrac18 & & |i-j|=1 \\ \tfrac{1}{16} & & |i-j| \ge 2 \end{array} \right.$ and hence $\begin{array}{rcl} \displaystyle E[X^2] \; = \; \sum_{i,j} E[X_iX_j] & = & \tfrac14\times (n-1) + \tfrac18 \times 2(n-2) + \tfrac{1}{16} \times (n-2)(n-3) \\ & = & \tfrac{1}{16}(n^2 + 3n - 6) \end{array}$ so that $\mathrm{Var}[X] \; = \; E[X^2] - E[X]^2 \; =\; \tfrac{1}{16}(5n-7)$ With $n=100$ , the variance is $\tfrac{493}{16}$ , and so the answer is $\boxed{509}$ .