How many coin tosses to get X Heads in a row? — Quantitative Problems on Markov Chains

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, <ul> <li>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)</li> <li>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)</li> </ul> This means, E[n] = (p) ( E[n-1] + 1 )+ (1-p)( 1 + E[n-1] + E[n] ) <a href="https://medium.com/@harshraj11584/quantitative-problems-on-markov-chains-8d6636ffcd90">Website</a>