I'm writing an algorithm for a coin toss problem. But I have a problem understanding the calculation given.
Here is the question:
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?
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.
Now my problem is understanding the calculation: 1 + (0.5 * 0 + 0.5 * 6) = 4.0
when N = 2 and M = 1. I understood how they got the 6 (which is basically calculating it when M = 0, formula here).
Now what if I'm going to calculate N = 3, M = 1
or N = 3, M = 2
?
Could someone write this calculation in a formula for me please? What is the 1
? What is (0.5 * 0 + 0.5 * 6)
?