Probability Theory – Problem 23: Find and

Consider a biased coin that lands heads with probability $p$ and tails with probability $1-p$, where the outcomes are recorded as ``$H$'' for heads and ``$T$'' for tails. 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}]$ and $\mathrm{Var} (N_{HH})$. (Hint: There are two approaches. The first 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 second approach is to show that $N_{H}$ and $N_{HH|H}$ are independent, and then construct the probability generating function of $N_{HH|H} - N_{H}$ to solve the problem.)

Let $N_{HH}$ denote the number of tosses required for two consecutive heads (HH) to appear for the first time. 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 pattern "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 toward the pattern 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 the pattern "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 outcome is "HT" and the process has not terminated. Two tosses have been used, but the accumulated "H" has been broken, so the process restarts from scratch. Hence the expected total number of tosses in this case is $2+E$. By the law of total expectation, $E$ can be expressed as 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 tosses from a fresh start until "HH" appears, having the same distribution as $N_{HH}$. Taking the expectation of the square yields $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 yields $E[(2+N'')^2] = E[4+4N''+(N'')^2] = 4+4E[N''] + E[(N'')^2] = 4+4E+S$. Combining the cases above, we obtain 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}$. Using the variance formula $Var(N_{HH}) = E[N_{HH}^2] - (E[N_{HH}])^2$, we compute the variance: $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}$.