Skip to content

Head density in tosses with no two heads adjacent

Question

A fair coin is tossed nn times, and you learn that the resulting sequence never has two heads in a row. Let E(n)E(n) be the conditional expected number of heads. The limit lim⁡n→∞E(n)/n\lim_{n\to\infty} E(n)/n equals ab+c\dfrac{a}{b+\sqrt{c}} for integers a,b,ca,b,c with cc as small as possible. Compute abcabc.

Short answer

5050. Conditioning makes all valid strings equally likely, and they are counted by Fibonacci numbers. Counting heads through the recursion (a string starts with T or with HT) shows the head fraction tends to 1φ+2=25+5\tfrac{1}{\varphi+2}=\tfrac{2}{5+\sqrt5}, where φ\varphi is the golden ratio. So a=2a=2, b=5b=5, c=5c=5 and abc=50abc=50.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free