HMMT 二月 2012 · COMB 赛 · 第 7 题

HMMT February 2012 — COMB Round — Problem 7

You are repeatedly flipping a fair coin. What is the expected number of flips until the first time that your previous 2012 flips are ‘HTHT...HT’ ?

解析

You are repeatedly flipping a fair coin. What is the expected number of flips until the first time that your previous 2012 flips are ‘HTHT...HT’ ? 2014 Answer: (2 − 4) / 3 Let S be our string, and let f ( n ) be the number of binary strings of length n which do not contain S . Let g ( n ) be the number of strings of length n which contain S but whose prefix of length n − 1 does not contain S (so it contains S for the “first” time at time n ). Consider any string of length n which does not contain S and append S to it. Now, this new string contains S , and in fact it must contain S for the first time at either time n + 2, n + 4, ..., or n + 2012. It’s then easy to deduce the relation f ( n ) = g ( n + 2) + g ( n + 4) + · · · + g ( n + 2012) Now, let’s translate this into a statement about probabilities. Let t be the first time our sequence of n coin flips contains the string S . Dividing both sides by 2 , our equality becomes 2012 P ( t > n ) = 4 P ( t = n + 2) + 16 P ( t = n + 4) + · · · + 2 P ( t = n + 2012) Summing this over all n from 0 to ∞ , we get ∑ 2012 2014 P ( t > n ) = 4 + 16 + · · · + 2 = (2 − 4) / 3 ∑ But it is also easy to show that since t is integer-valued, P ( t > n ) = E ( t ), and we are done.