Head density with no two in a row

Flip a fair coin nn times, conditioned on the event that no two consecutive heads ever appear. Let E(n)E(n) be the expected number of heads under this conditioning. Compute limnE(n)n\displaystyle\lim_{n\to\infty}\frac{E(n)}{n}. It equals ab+c\dfrac{a}{b + \sqrt{c}} for integers a,b,ca, b, c with cc minimal; find abca\,b\,c.

Show hints (2)+
  1. No-HH strings of length nn are uniform and number Fn+2F_{n+2}; use a transfer matrix (states: last flip T/H).
  2. The head density converges to 5510=25+5\tfrac{5-\sqrt5}{10}=\tfrac{2}{5+\sqrt5} - read off a,b,ca,b,c.

Answer

Reveal answer →

50

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Asked at: Jane Street, Two Sigma

Related questions