Consider a biased coin that lands heads with probability and tails with probability . We use `` '' and `` '' to record heads and tails, respectively. The coin is tossed repeatedly. Let denote the number of tosses required for the pattern `` '' to appear for the first time. Find . (Hint: There are two approaches. One is to compute conditional expectations and then use the law of total expectation to compute separately to obtain the result. The other approach is to try to prove that and are independent, and then construct the generating function of to solve the problem.)

The expectation is . The variance is .

Probability Theory Solution – Problem 54: Find

Question

Consider a biased coin that lands heads with probability $p$ and tails with probability $1-p$ . We use `` $H$ '' and `` $T$ '' to record heads and tails, 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 use the law of total expectation to compute $\mathbb{E}[N_{HH}],\mathbb{E}[N_{HH}^2]$ separately to obtain the result. The other approach is to try to prove 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.)

Step-by-step solution

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), with probability $1-p$ : one toss has been made but no progress toward "HH" has occurred; the process effectively restarts. Thus the expected total number of tosses from this point is $1+E$ . If the first toss is heads (H), with probability $p$ : one toss has been made and one step of progress toward the goal. Now consider the second toss. If the second toss is heads (H), with probability $p$ : the pattern "HH" has appeared and the process terminates. The total number of tosses is $2$ . If the second toss is tails (T), with probability $1-p$ : the pattern "HT" has appeared; the process has not ended. Two tosses have been made, but the accumulated "H" is broken, and the process effectively restarts. Thus the expected total number of tosses from this point is $2+E$ . By the law of total expectation, expressing $E$ as the weighted average of the expected values over all possible 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, decompose $N_{HH}^2$ : 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: $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), 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: $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 simplifying: $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 $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$ : $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}$

Final answer

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}$ .

Marking scheme

The following is the grading rubric tailored for this probability problem. This rubric treats the official solution as fully correct.

1. Checkpoints (max 7 pts total)

Score exactly one chain | take the maximum subtotal among chains; do not add points across chains.

Chain A: Conditional Expectation Method / System of Equations (Official Solution Path)

Expectation equation setup [2 pts] [Additive]: Correctly writing the recursive equation for $E = \mathbb{E}[N_{HH}]$ .
For example: $E = (1-p)(1+E) + p[p \cdot 2 + (1-p)(2+E)]$ or an equivalent expanded/simplified form.
*Note: If only the equation structure is correct (reflecting the restart and step-counting logic) but the coefficients have minor errors, award 1 pt.*
Expectation solution [1 pt] [Additive]: Correctly solving $E = \frac{1+p}{p^2}$ .
Second moment equation setup [2 pts] [Additive]: Correctly writing the recursive equation for $S = \mathbb{E}[N_{HH}^2]$ .
Key requirement: Must correctly expand the squared expectation $\mathbb{E}[(N+k)^2] = \mathbb{E}[N^2] + 2k\mathbb{E}[N] + k^2$ (i.e., reflecting $S + 2kE + k^2$ ).
*If the cross term $2kE$ is omitted (i.e., incorrectly writing $\mathbb{E}[(N+k)^2] = S + k^2$ ), no credit for this item or subsequent computation items.*
Second moment solution [1 pt] [Additive]: Substituting $E$ and correctly solving $S = \frac{-p^3 - p^2 + 4p + 2}{p^4}$ (or a correct equivalent intermediate expression).
Final variance result [1 pt] [Additive]: Using $\mathrm{Var} = S - E^2$ to combine and algebraically simplify, obtaining the final result $\frac{-p^3 - 2p^2 + 2p + 1}{p^4}$ .

Chain B: Probability Generating Function (PGF) Method

PGF equation setup [2 pts] [Additive]: Correctly establishing the self-referential equation for $G(z) = \mathbb{E}[z^N]$ .
For example: $G(z) = (1-p)zG(z) + p(1-p)z^2G(z) + p^2z^2$ .
PGF closed-form expression [1 pt] [Additive]: Correctly solving for the explicit form of $G(z)$ , e.g., $G(z) = \frac{p^2z^2}{1 - (1-p)z - p(1-p)z^2}$ .
Expectation computation [1 pt] [Additive]: Correctly computing $\mathbb{E}[N_{HH}] = \frac{1+p}{p^2}$ via $G'(1)$ .
Second derivative / second moment computation [2 pts] [Additive]: Correctly differentiating $G(z)$ twice to compute $G''(1)$ or $\mathbb{E}[N(N-1)]$ , showing a correct and complete calculus derivation.
Final variance result [1 pt] [Additive]: Combining the above results to correctly compute $\mathrm{Var}(N_{HH}) = \frac{-p^3 - 2p^2 + 2p + 1}{p^4}$ .

Total (max 7)

2. Zero-credit items

Only listing the standard geometric distribution formula (e.g., $1/p$ or $(1-p)/p^2$ ) without deriving anything specific to the "HH" pattern.
Only listing the definition of expectation or variance (e.g., $\sum x P(x)$ ) without any specific substitution or computation for this problem.
Writing the answer directly without proof, and the answer is incorrect.

3. Deductions

Arithmetic error [-1]: After setting up the correct equation, a simple algebraic or sign error leads to an incorrect final result (one deduction per error, but at most 1 per chain).
Logical gap [Cap at 3/7]: In Chain A, if the cross term ( $2kE$ ) arising from the square expansion is omitted when computing the second moment $S$ , this is a core logical error; that part and the subsequent variance part receive no credit (score capped at the expectation portion of 3 pts).
Unsimplified result [No Penalty]: If the final result is in a correct form (e.g., written as a difference of fractions) but not combined into the single-fraction form of the official answer, no penalty is applied as long as it is mathematically equivalent.

Probability Theory – Problem 54: Find