Probability Theory – Problem 5: Find

Consider a biased coin that lands heads with probability $p$ and tails with probability $1-p$, where the outcomes are recorded as ``$H$'' and ``$T$'' respectively. The coin is tossed repeatedly. Let $N_{HH}$ denote the number of tosses required for the pattern ``$HH$'' to appear for the first time. Find $\mathbb{E}[N_{HH}],\mathrm{Var} (N_{HH})$. (Hint: There are two approaches. One is to compute conditional expectations and then apply the law of total expectation to calculate $\mathbb{E}[N_{HH}]$ and $\mathbb{E}[N_{HH}^2]$ separately, thereby obtaining the result. The other approach is to show that $N_{H}$ and $N_{HH|H}$ are independent, and then construct the generating function of $N_{HH|H} - N_{H}$ to solve the problem.)

Let $N_{HH}$ denote the number of tosses until two consecutive heads (HH) first appear. The coin lands heads with probability $p$ and tails with probability $1-p$. Let $E = E[N_{HH}]$. Consider the outcome of the first toss. If the first toss is tails (T), which occurs with probability $1-p$, then one toss has been used but no progress has been made toward the goal "HH"; the process effectively restarts from scratch. Hence the expected total number of tosses in this case is $1+E$. If the first toss is heads (H), which occurs with probability $p$, then one toss has been used and one step of progress has been made. We now consider the outcome of the second toss. If the second toss is heads (H), which occurs with probability $p$, then "HH" has appeared and the process terminates. The total number of tosses is $2$. If the second toss is tails (T), which occurs with probability $1-p$, then the pattern "HT" has occurred and the process has not terminated. Two tosses have been used, but the accumulated "H" has been broken, so the process restarts from scratch. The expected total number of tosses in this case is $2+E$. By the law of total expectation, $E$ equals the weighted average of the expected values over all cases: $E = (1-p) \cdot (1+E) + p \cdot [p \cdot 2 + (1-p) \cdot (2+E)]$ Solving for $E$: $E = 1 - p + (1-p)E + 2p^2 + (2p-2p^2) + (p-p^2)E$ $E = \frac{1+p}{p^2}$ Therefore, $E[N_{HH}] = \frac{1+p}{p^2}$. Let $S = E[N_{HH}^2]$. Using the law of total expectation, we decompose $N_{HH}^2$ as follows: If the first toss is tails (T), the total number of tosses is $1+N'$, where $N'$ is the number of additional tosses from a fresh start until "HH" appears, having the same distribution as $N_{HH}$. Taking the expectation of the square gives $E[(1+N')^2] = E[1+2N'+(N')^2] = 1+2E[N'] + E[(N')^2] = 1+2E+S$. If the first toss is heads (H), we consider the second toss: If the second toss is heads (H), the total number of tosses is $2$, and its square is $4$. If the second toss is tails (T), the total number of tosses is $2+N''$, where $N''$ has the same distribution as $N_{HH}$. Taking the expectation of the square gives $E[(2+N'')^2] = E[4+4N''+(N'')^2] = 4+4E[N''] + E[(N'')^2] = 4+4E+S$. Combining the above cases yields the equation for $S$: $S = (1-p) \cdot (1+2E+S) + p \cdot [p \cdot 4 + (1-p) \cdot (4+4E+S)]$ Expanding and collecting terms in $S$: $S = (1-p)(1+2E) + (1-p)S + 4p^2 + p(1-p)(4+4E) + p(1-p)S$ $S - (1-p^2)S = 1+3p + (2+2p-4p^2)E$ $p^2 S = 1+3p + 2(1+p-2p^2)E$ Substituting the previously obtained $E = \frac{1+p}{p^2}$: $p^2 S = 1+3p + 2(1+p-2p^2)\frac{1+p}{p^2}$ Multiplying both sides by $p^2$ to clear the denominator: $p^4 S = p^2(1+3p) + 2(1+p-2p^2)(1+p)$ $p^4 S = -p^3 - p^2 + 4p + 2$ Therefore, $E[N_{HH}^2] = S = \frac{-p^3 - p^2 + 4p + 2}{p^4}$. Computing the variance via $Var(N_{HH}) = E[N_{HH}^2] - (E[N_{HH}])^2$: $Var(N_{HH}) = \frac{-p^3 - p^2 + 4p + 2}{p^4} - \left(\frac{1+p}{p^2}\right)^2$ $Var(N_{HH}) = \frac{-p^3 - 2p^2 + 2p + 1}{p^4}$

The expectation is $E[N_{HH}] = \frac{1+p}{p^2}$. The variance is $Var(N_{HH}) = \frac{1+2p-2p^2-p^3}{p^4}$.