# Expected number of tosses to get 100 consecutive Heads [closed]

Assume a fair coin. What is the expectation number of tosses 𝑋 until getting 100 consecutive heads?

I have looked a similar problem to get 3 or 5 consecutive heads. But I don't know how to apply it to a more common case.

• What have you tried so far? – Klangen Sep 2 '19 at 16:40
• Well, you could set it up recursively. Get $E_{100}$ in terms of $E_{99}$ and so on. I expect that's easier than getting a closed form from first principles (of course the recursion isn't hard to solve so you could use it to get a closed form). – lulu Sep 2 '19 at 16:56
• But, really, if you have studied the cases for $n=3$ and $n=5$ you ought to know how to solve it for any $n$. – lulu Sep 2 '19 at 17:00

Lets take an example: finding the expected number of flips it will take for getting two consecutive heads.

If the expected number of coin flips is denoted by $$x$$, $$x=(\frac{1}{2}$$)($$x+1$$)$$+$$($$\frac{1}{4}$$)$$(x+2)$$+$$(\frac{1}{4})(2)$$ $$= 6$$

This is because there are three scenarios. First, there is a $$\frac{1}{2}$$ probability that the first flip comes up as tails, resulting in 1 being added to the expected number of flips, $$x$$. This is the first part of the expression, $$(\frac{1}{2}$$)($$x+1$$). Next, if the first flip results in heads, but the second flip results in tails, two flips have been wasted, and the probability of this occurrence is $$\frac{1}{4}$$. This is denoted by $$(\frac{1}{4}$$)($$x+2$$). Lastly, if both flips are heads, two flips are used, and the probability of the event is $$\frac{1}{4}$$. This is shown with "$$(\frac{1}{4})(2)$$". All these elements are added together, due to the rule of linearity for expected values, to get $$x = 6$$.

With this example, we can generalize the equation, for the number of consecutive heads required being $$n$$.

If the $$p$$th flip in an attempt is a tails, the entire process is reset, and the expression for that attempt is $$(\frac{1}{2^p}$$)($$x+p$$). If $$n$$th flip is tails, the expression would be $$(\frac{1}{2^n}$$)($$x+n$$). If $$n$$ consecutive heads are achieved, the expression would be $$(\frac{1}{2^n}$$)$$(n)$$. Combining these results in $$x =$$ $$(\frac{1}{2}$$)($$x+1$$)$$+$$($$\frac{1}{4}$$)$$(x+2)$$+$$(\frac{1}{4})(2)$$ $$...$$ $$(\frac{1}{2^p}$$)($$x+p$$) $$...$$ $$(\frac{1}{2^n}$$)($$x+n$$) $$+$$ $$(\frac{1}{2^n}$$)$$(n)$$ $$=$$ $$2^{n+1} - 2$$

You can find more detailed explanations and more examples here: https://www.codechef.com/wiki/tutorial-expectation

And another way to solve it here: Is my answer correct? Expected number of coin flips to get 5 consecutive heads

• Thank you so much. Your answer really makes sense to me. – yixi zhou Sep 2 '19 at 21:36