HMMT 二月 2012 · COMB 赛 · 第 7 题

英文解析

7. You are repeatedly flipping a fair coin. What is the expected number of flips until the first time thatyour 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 lengthn which do not contain S . Let g ( n ) be the number of strings of length n which contain S but whoseprefix 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 stringcontains 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 relationf ( 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 ofncoin 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.