How many tosses to get 2 heads

Question: Given a fair coin, how many tosses on average do you need to get 2 heads?

Heuristic based solution:

This is based on the general principle of conditional averages and dependency/independence between events.

Suppose
E(x) = average tosses needed to have 2 heads
E(x|H) = average total tosses needed to have 2 Heads when the first toss is Head
E(x|T) = average total tosses needed to have 2 Heads when the first toss is Tail
E(x|HH) =average total tosses needed to have 2 Heads when the first two tosses are heads = 2
E(x|HT) = average total tosses needed to have 2 Heads when the first two tosses are HT
Then we have the following relationships:
E(x|T) = 1 + E(x) (The first toss is wasted so we are back to nothing)
E(x|HT) = 2 + E(x) (The first two tosses are wasted and we are back to square 1)
Further, we have the following relationship:
E(X) = 0.5 E(x|H) + 0.5 E(x|T)
= 0.5 { 0.5 E(x|HH) + 0.5 E(x|HT)} + 0.5 (1 + E(x))
= 0.5 { 0.5*2 + 0.5 [2 + E(x)]} + 0.5 + 0.5 E(x)
= 1 .5 + 0.75 E(x)
Solving the equation, we get E(x) = 6, meaning on average 6 tosses are needed to get 2 heads.

If the question is for 3 or more consecutive patterns, similar approach can be used. But the number of iteration needed will be more than the two levels we show here.

Markov chain based solution:




As shown in the above figure, define a Markov chain that is formed by the following three states:
S1: the previous tossing generates Tail ;
S2: the previous tossing generates Head;
S3: after current tossing, we get two consecutive Hs.



Then, the probability transition matrix, denoted by P, is represented in the first equation above.

It can also be seen that S3 is an absorbing state. What we need to calculate is the average steps need to reach the absorbing state. We use hi to denote the average number tosses needed to move from state Si to S3 (also known as average hitting time). Clearly, we have h3 = 0. Then, we have the second equation shown above.

Basically, this is based also on the principle of conditional expectation also. The left side is a decomposition of the first toss and what happens after the first toss.
Solving this equation, we get h1 = 6; h2 = 4.
Then the expected number X of tosses to get two heads in a row is given by the third equation above, meaning on average 6 tosses are needed to get 2 consecutive heads.

The same method can be generalized to calculate the average number of tosses to get N heads in a row. The states in the Markov chain will be all the initial sequence of the final N heads. For example, N=3 means the following state (H, T, HH, HHH). Another example, if we want to calculate the same for HTH, then the Markov chain is formed by (T, H, HT, HTH).