15
$\begingroup$

I recently had this question in an interview:

You are flipping a fair coin until a sequence of four flips repeats itself. The sequences are allowed to overlap. What is the expected number of flips?

For example, if you flip HTHTHT, the sequence HTHT appears in flips 1-4 and 3-6. In this case, we are done after 6 flips. As another example, if you flip HHTTHHTT, the sequence HHTT repeats in flips 1-4 and 5-8, and we are done after 8 flips. What is the expected number of flips?

I've been thinking about this question for a few days now, and I haven't come to an answer. I've tried the simpler problem where we consider a sequence of two flips instead of four flips, but it is still rather difficult. I suspect that there is a nice recursive way to solve this problem, but I can't figure it out.

I am also interested in generalizations of this problem. For example, what is the expected number of flips for a sequence of $n$ to repeat itself? What happens if the coin isn't fair?

I have another interview in a few days, so I would very much like to see how to solve this problem in advance. Any help is appreciated.

Edit:

Based on computational evidence (assuming I didn't make a mistake in the code), it appears that the expected number of flips is about 9.81. I would like to know the exact answer, as well as an analytic solution to this problem.

Edit 2:

Another piece of information that may be of use: I had 30 seconds to answer the question. This makes me believe that there is some "easy" way to get the answer, or they were looking for an approximate answer.

Edit 3:

@r.e.s. has kindly provided exact solutions for $n=1,2,3,4,5$. For $n=6$, numerical computation seems to indicate that the answer is around $18.977$ or $18.978$. I will be updating periodically with approximations for other values of $n$.

Edit 4:

$$ \begin{array}{|c|c|} \hline n & E(L_{n}) \\ \hline 1 & \frac{5}{2}\\ \hline 2 & \frac{35}{8}\\ \hline 3 & \frac{435}{64}\\ \hline 4 & \frac{2513}{256}\\ \hline 5 & \frac{57922047}{4194304}\\ \hline 6 & \approx 18.9775\\ \hline 7 & \approx 25.928\\ \hline 8 & \approx 35.288\\ \hline \end{array} $$

$\endgroup$
  • 1
    $\begingroup$ Well in general for length $n$, we must have at least $n+1$ tosses to find a repeat and at most $n+2^n-1$ tosses to not find a repeat (because there are $2^n$ possible sequences total and $k-n+1$ (not necessarily distinct) sequences contained within a sequence of length $k$). $\endgroup$ – Jacob Apr 15 '18 at 0:54
  • $\begingroup$ Perhaps thinking about it like this may help: after $n+k$ tosses, if we have not already found a repeated sequence then we have a list of $k+1$ sequences of length $n$ so far. For it to be possible for the next toss to be a repeat, the last $n-1$ tosses must have repeated already. If it has repeated twice we have a 100% probability of getting a repeat the next toss; if it has repeated once we have a 50% chance of getting a repeat the next toss. Otherwise, we have a 0% chance of getting a repeat the next toss and a new sequence of length $n$ (2 possible) will be added to our list $\endgroup$ – Jacob Apr 15 '18 at 1:25
  • $\begingroup$ Unfortunately I just lost a great deal of progress on an answer due to an unexpected power short, but I can say that the best way to approach this problem is by looking at how you end up with repeating subsequences. If a sequence of length $n+p$ terminates, either every $p$th flip matches each other or the sequence starting at $p$ matches the rule for length $n+p-1$. There is overlap here. Additionally, once $p\gt n$, the sequence of flips from 0 to $p$ might include a subsequence found later in the string. Due to the fact that the maximal flip length is exponential, it comes quick. $\endgroup$ – LuuBluum Apr 15 '18 at 3:07
  • $\begingroup$ It seems that de Bruijn sequences: en.wikipedia.org/wiki/De_Bruijn_sequence are very similar to what you're looking at here. For any given de Bruijn sequence, you can append the first n-1 terms to the end of the sequence to yield the same result disregarding cycles. In that case, the number of "worst case" sequences would be $\frac{2^{2^{n-1}}}{2^n}$. Keep in mind, that's the number of sequences maximally long that do not terminate. For every one of those, there are 2 that do. Hence, you have $\frac{2^{2^{n-1}}}{2^{n-1}}$ worst cases. There might be repeats. $\endgroup$ – LuuBluum Apr 15 '18 at 20:32
  • $\begingroup$ An observation that may or may not be useful: Assume $p=1/2$, the probability that two 4-bit sequences are equal = 1/16 if the sequences do not overlap, obviously. However, from my calculations, it seems the prob is STILL 1/16 even if they overlap! E.g. the 1234 sequence = the 2345 sequence for any pattern aaaaa (where a can be H or T), so prob = 1/16. Similarly, if they overlap by 2 bits, the required pattern is ababab (where a, b = H or T and they can be different or same), so again 1/16 probability, and for overlap by 1 bit the required pattern is abcabca, again 1/16 probability. $\endgroup$ – antkam Apr 16 '18 at 21:30
3
+50
$\begingroup$

I would like to know the exact answer, as well as an analytic solution to this problem.

Here's the exact answer as a function of $p=\Pr(\text{H})$, for several values of $n$. Let $L_n$ denote the length of the sequence when it first contains a repeated word of length $n$. By directly enumerating the possible sequences, we find (using Sage) the following exact results:

n   E(L_n | p=1/2)    E(L_n | p)
-   ----------------  -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1   5/2               -2*p^2 + 2*p + 2
2   35/8               2*p^4 - 4*p^3 - 3*p^2 + 5*p + 3
3   435/64             16*p^8 - 64*p^7 + 61*p^6 + 41*p^5 - 90*p^4 + 37*p^3 - 10*p^2 + 9*p + 4
4   2513/256          -64*p^18 + 576*p^17 - 1880*p^16 + 1984*p^15 + 3094*p^14 - 10682*p^13 + 9560*p^12 + 2050*p^11 - 9950*p^10 + 6696*p^9 - 841*p^8 - 898*p^7 + 420*p^6 + 8*p^5 - 129*p^4 + 54*p^3 - 12*p^2 + 14*p + 5
5   57922047/4194304  -13312*p^34 + 226304*p^33 - 1690752*p^32 + 7137280*p^31 - 17544144*p^30 + 18701616*p^29 + 29742468*p^28 - 163840744*p^27 + 339947916*p^26 - 413989056*p^25 + 268118367*p^24 + 32316996*p^23 - 278576119*p^22 + 333006671*p^21 - 241401935*p^20 + 128354791*p^19 - 59474305*p^18 + 28069920*p^17 - 12055855*p^16 + 2638562*p^15 + 1497144*p^14 - 1982176*p^13 + 1101961*p^12 - 307798*p^11 - 27907*p^10 + 68859*p^9 - 31985*p^8 + 9681*p^7 - 3530*p^6 + 1571*p^5 - 678*p^4 + 195*p^3 - 26*p^2 + 20*p + 6

In particular, we have the exact expectation $\text{E}(L_4 | p={1\over 2})=2513/256 = 9.8164...$

(Cross-check: Monte Carlo simulations for $n=1,2,3,4,5$ are consistent with these numerical values to three three significant figures.)


The "direct enumeration" method calculates the expectation as follows, using $1$ and $0$ to represent $\text{H}$ and $\text{T}$ respectively:

Let $S_n$ denote the set of all the possible binary sequences obtainable by flipping the coin until a length-$n$ repetition occurs. Now $L_n$ is just the length of such a sequence, so $$\begin{align}\text{E}(L_n\mid p)&=\sum_{s\in S_n}\text{length}(s)\Pr(s)\\[2ex] \end{align}$$ where $$\Pr(s) = p^{\text{sum}(s)}(1-p)^{\text{length}(s)-\text{sum}(s)}$$ with $\text{sum}(s)$ being the number of $1$s in $s$, and $\text{length}(s)-\text{sum}(s)$ being the number of $0$s in $s$.

The program at the above-given link implements this by starting with a list of all length-$n$ sequences, then "growing" each of them in all possible ways by appending bits, until they stop growing when a repetition occurs. The result (stop_seqs(n)) is a listing of the set $S_n$, from which the expectation is calculated by the above summation.


Apparently, no closed-form solution is known for arbitrary $n$, even in the case of a fair coin; however, asymptotic results for this case have been obtained, e.g., by Karnin, E. (1983), who showed that $$E\left(L_n\,{\Large\vert}\,p={\small{1\over 2}}\right)\sim\sqrt{\pi\,2^n},\ \text{ as }n\to\infty,$$ which is just to say $$\lim_{n\to\infty}{E(L_n\mid p={1\over 2}) \over \sqrt{\pi\,2^n}}=1.$$

But this is a poor approximation in your case of $n=4$, since $\sqrt{\pi\,2^4}=7.0898\ldots,$ whereas the exact value (by direct enumeration) is $\text{E}(L_4\mid p={1\over 2})=2513/256 = 9.8164\ldots$

Following is a plot of the ratio $E(L_n\mid p={1\over 2}) \over \sqrt{\pi\,2^n}$ for $1\le n\le 20$, using expected values correct to three significant figures from Monte Carlo simulation when $n>5$:

plot of E(L_n)/sqrt(pi*2^n)

Ironically, the ratio equals $0.997...$ when $n=1$, but does not again get this close to $1$ for $n\le 20.$


NB: I strongly suspect that the interviewer's intended question was the following remarkable variant, obtained by changing just one word of the quoted paragraph (especially since in both examples it is the initial sequence of four flips that repeats):

You are flipping a fair coin until the initial sequence of four flips repeats itself. The sequences are allowed to overlap. For example, if you flip HTHTHT, the sequence HTHT appears in flips 1-4 and 3-6. In this case, we are done after 6 flips. As another example, if you flip HHTTHHTT, the sequence HHTT repeats in flips 1-4 and 5-8, and we are done after 8 flips. What is the expected number of flips?

The answer to this revised version is the integer $n+2^n$ (where $n$ is the initial-segment length, e.g. $n=4$), no matter what may be the value of $p=\Pr(\text{H})$ -- assuming that $p$ is constant, $0<p<1$, and that the tosses are independent!

This general result can be proved by a minor variation of the proof of Theorem 2 in this online article. The special case of $p={1\over 2}$ can be proved by the following argument given in the above-linked article by Karnin: Considering the words to be states of a Markov chain, the transition matrix is seen to be doubly stochastic, which implies that the invariant distribution assigns to each state the same probability $2^{-n}$; consequently, the expected waiting time (after the initial segment is formed) is the reciprocal of this, i.e., $2^n$, and the expected total waiting time is therefore $n+2^n.$

$\endgroup$
  • $\begingroup$ That is an astonishing amount of cancellation to get from a leading term that's a multiple of $2^{-18}$ (and a multiplied-out leading term of $2^{-12}$) to only having a factor of $2^{-8}$ in the final result. It definitely makes me wonder if there's something more going on. $\endgroup$ – Steven Stadnicki Apr 15 '18 at 15:56
  • $\begingroup$ Direct enumeration is definitely one way to go. However, I was only given 30 seconds to answer, so this would not be the best way, in my case. Nonetheless, thank you for your input. $\endgroup$ – Mark Apr 15 '18 at 16:01
  • $\begingroup$ My own counting with $p={1\over2}$, using Mathematica, arrived at ${2513\over256}$ as well. $\endgroup$ – Christian Blatter Apr 15 '18 at 18:40
  • $\begingroup$ Could you explain exactly how you solve using Sage? $\endgroup$ – Royi Apr 17 '18 at 8:17
  • 1
    $\begingroup$ @Royi I've added an explanation of the enumeration method, but I think it would not be appropriate here to go into implementation details of the program. (In case you missed it: I included a link to the briefly-commented program available online.) $\endgroup$ – r.e.s. Apr 17 '18 at 14:25

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.