Interviewstreet had their second CodeSprint in January that included the question below. The programmatic answer is posted but doesn't include a statistical explanation.
(You can see the original problem and posted solution by signing in to the Interviewstreet website with Google creds and then going to the Coin Tosses problem from this page.)
You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads.
What is the expected number of additional tosses needed until you get N consecutive heads?
The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.
If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0 If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.
All of the mathematical equations I came up with had the right answers for the sample input data listed above, but was wrong for all of their other input sets (which are not known). Their programmatic solution appears to solve the problem far differently from my try-to-come-up-with-an-equation method. Can someone please explain how to come up with an equation that would solve this?