(HMMT 2012) 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’?

Could someone tell me what's wrong with my solution using recursion and Markov Chains?

Define $n$ states corresponding to the $2013$ stages of 'HTHT...HT' (including the "$0$th" state, which is the start). Let $a_n$ denote the expected value of reaching the string at state $n$. For example, $a_3$ is the expected number of flips to reach 'HTHT...HT' given that the previous 3 flips were 'HTH.' Therefore, we want to find $a_0$.

Now we define the recursion $a_{n-1} = \frac{1}{2}(a_n+1)+\frac{1}{2}(a_{0}+1)$. From any state $a_{n-1}$, there is a $\frac{1}{2}$ chance that it will go to the next wanted element in the string, and this takes one flip. Similarly, there is a chance that it will go the wrong element, which brings the state back to state 0.

Note that $a_{2012} = 0$. $a_{2011} = \frac{1}{2}(a_0+2), a_{2010} = \frac{3}{4}(a_0+2), a_{2009} = \frac{7}{8}(a_0+2)$ From here, it's not difficult to prove with induction that $a_{2012-n} = \frac{2^k-1}{2^k}(a_0+2)$.

$a_0 = \frac{2^{2012}-1}{2^{2012}}(a_0+2)$

$a_0 = 2^{2013}-2$

Since the problems asks for the first time that the previous 2012 flips satisfy the condition, we add 1: $\fbox{$2^{2013}-1$}$

However, the correct solution is $\frac{(2^{2014} − 4)}{3}$.


One possible flaw, let's see how can we possibly mess up.

If we toss $HTHTT$, we messed up and we have to start from nothing. We go to state $0$.

If we toss $HTHTHH$, we messed up, but we start with a given $H$. We go to state $1$.

Hence we need not always go back to state $0$. It depends on the parity of the location that we fail.

  • $\begingroup$ Oh, I forgot to consider this case. Thanks for clearing that up. $\endgroup$ – dcxt Jul 16 '17 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.