Let E[n] = Number of tosses needed to get n Heads in a row.
Let’s say we have n-1 consecutive heads so far, and are at State n-1. If we do 1 more toss,
- We reach State n with probability p. This is the terminal state, no more tosses needed. Contribution in number of tosses = E[n-1] + 1.
(Why? 1 for this toss, E[n-1] for tosses so far) - Or we reach State 0 with probability 1-p. We need n more consecutive heads. Contribution in number of tosses = 1 + E[n-1] + E[n].
(Why ? 1 for this toss, E[n-1] for tosses so far, and E[n] for more tosses needed)
This means, E[n] = (p) ( E[n-1] + 1 )+ (1-p)( 1 + E[n-1] + E[n] )