3
$\begingroup$

Assume you have a fair coin. What's the expected number of coin tosses in order to get a sequence HHTTHH? (H=head,T=tail).

Assuming you start tossing and keep going until your last six tosses match the sequence.

I want to know if there is a general formula for this kinds of problems?

$\endgroup$
  • $\begingroup$ Do you want HHTHHH to appear as a subsequence anywhere in a long list of tosses, or do you do 6 tosse, and then restart the sequence? $\endgroup$ – Larry D'Anna Mar 24 '13 at 5:35
  • $\begingroup$ You will do a long list of tosses, as long as you get HHTTHH, you will stop, count on average how many times you need to toss in order to get HHTTHH. $\endgroup$ – nkhuyu Mar 24 '13 at 5:42
  • $\begingroup$ This has been asked on the site several times before and several methods to solve every similar problem have been detailed in answers. Did you look for them before asking? $\endgroup$ – Did Mar 24 '13 at 10:16
  • $\begingroup$ @nkhuyu don't use comments to add detail to your question. It should be in the body of the question. I've done this for you already. $\endgroup$ – Warren Hill Jan 24 '18 at 19:12
7
$\begingroup$

The answer is $70=2^{\color{red}{6}}+2^{\color{red}{2}}+2^{\color{red}{1}}$. The integers $6$, $2$ and $1$ are the lengthes of the prefixes of the word HHTTHH that are also its suffixes, here HHTTHH, HH and H.

For more details, see some previous posts on the site about this exact model, or the book DNA, Words and Models by Robin, Rodolphe, and Schbath (2005), or the survey Enumeration of strings (1985) by A. Odlyzko (see section 4, citing the paper A combinatorial identity and its application to the problem concerning the first occurrences of a rare event (1966) by A. D. Solov’ev).

$\endgroup$
-1
$\begingroup$

The correct answer is 68. The expected value of any pattern W of length m, comprised of any symbols, W=w1w2..wm, is given by the following formula:

E[T]=[1/p(W)][1+Sum p(k) over all k such that k is a period of W],

where p(k)=p(w1)p(w2)...p(wk), and P(W)=p(m). In coin tossing experiments, only two symbols are involved, H and T. If W = HHTTHH, then W has only one period, k=4. Assuming a fair coin (which need not be assumed in using the formula), p(k)= p(4)=1/(2^4) and 1/p(W) = 2^6. Substituting these values into the above formula gives

E[T] = 2^6[1 + 1/(2^4)] = 2^6[17/(2^4)] = (2^2)(17) = 68.

$\endgroup$
  • 2
    $\begingroup$ Your answer would be significantly easier to read and understand if it were properly formatted using MathJax. As it is, I am having difficulty parsing how your solution which makes it difficult to see why your solution is different from the accepted solution. Given the discrepancy, a clearer explanation would be quite helpful. $\endgroup$ – Xander Henderson Jan 24 '18 at 19:16

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.