Medium | Probability |

What is the expected number of coin tosses required to get n consecutive heads?

Hint

That sum wont work! Just find the recursive relation.

Answer

En = 2En−1 + 2, giving En = 2^(n+1)-2

Solution

Define let Xn = number of tosses to get n consecutive heads; E(Xn) = expected number of coin tosses we require from now on, to get n consecutive heads. Recall the law of total probability,

E(Xn) = E ( E(Xn) |Y) )

where Y = current toss (either Head or tail).

En = (1/2)( E(Xn) | H) + (1/2)( E(Xn) | T)

En = (1/2)( E(X(n-1)) + 1 |H) + (1/2)( E(Xn) + 1 | T)

the extra 1 is because we just used a toss

En = 1 + (1/2)*E(n-1) + (1/2)*En

This above equation is logical and should be written directly.

=> En = 2E(n-1) + 2

This simplifies to 2^(n+1)-2 as E0 = 0. (not required)

E(Xn) = E ( E(Xn) |Y) )

where Y = current toss (either Head or tail).

En = (1/2)( E(Xn) | H) + (1/2)( E(Xn) | T)

En = (1/2)( E(X(n-1)) + 1 |H) + (1/2)( E(Xn) + 1 | T)

the extra 1 is because we just used a toss

En = 1 + (1/2)*E(n-1) + (1/2)*En

This above equation is logical and should be written directly.

=> En = 2E(n-1) + 2

This simplifies to 2^(n+1)-2 as E0 = 0. (not required)

Source: Top Quant Interview

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |