3

Consider tossing a fair coin and writing down the outcomes in a sequence of symbols. "H" stands for head and "T" for tail. Let A , B and C be the words HTHH , HHTH and THHH respectively. What is the probability of encountering each A, B and C as a subword in your sequence of outcomes before both others?

Edit: My question is relateted to this question. While its answers intuitively explain why some patterns hit sooner than others, none of them include a way of calculating those probabilities. Which is what I'm asking.

Edit 2: I have already recieved an answer. Having read the wikipedia articles, this question still stumps me. I'm starting a bounty on it.

Community
  • 1
superAnnoyingUser
  • 93
  • 1
  • 9
  • 4
    This is a variant of http://stats.stackexchange.com/questions/12174/time-taken-to-hit-a-pattern-of-heads-and-tails-in-a-series-of-coin-tosses and is solved using the same methods. (I'm sure I had seen this question asked and answered on Math.SE around the same time.) Regardless, SE requests that you post only a single copy of your question at a time. If you would like your question to appear here, then please ask the Math mods to migrate their version to this site. In the meantime--although this is not strictly correct--I have closed this version as a "duplicate." – whuber Mar 29 '13 at 15:06

3 Answers3

2

To avoid having to consider the initial steps you can start with the position after four tosses at which point each of the possible states has a probability of $1/16$.

You can turn your question into a Markov process with three absorbing states out of sixteen, and the non-absorbing states having a 0.5 chance of going to one of two other states, making the question arithmetic.

Run the Markov process by taking the 133rd or higher power of the transition matrix, and you will find that the three absorbing states have probabilities of about

  • HHTH 0.307692308
  • HTHH 0.326923077
  • THHH 0.365384615
Henry
  • 30,848
  • 1
  • 63
  • 107
  • Thank you, Henry. I'm not quite familiar with Markov processes. How should I turn my question to a Markov process? – superAnnoyingUser Apr 08 '13 at 17:57
  • 3
    Henry, those numbers approximate the rationals $16/52$, $17/52$, and $19/52$, respectively. They are obtained (in the usual way) from the eigenvectors associated with unit eigenvalues of the transition matrix. You only need $11$ states total (rather than $16$), because you might as well assume the process begins with an equal mixture of $HHH, HHT, \ldots, TTT$ and make transitions among these states and the three absorbing states. – whuber Apr 08 '13 at 19:58
  • @George: whuber's comment makes the point, and gives a better method of getting the same result. You need a transition matrix which shows that if you are at HHH then the probability of going to HHH or HHT is each 0.5. If you are at HHT then the probability of going to HTT or HTHH is each 0.5. If you are at HTHH then you stay there with probability 1. And so on. Wikipedia has articles on [Markov processes](http://en.wikipedia.org/wiki/Markov_process) and [transition matrices](http://en.wikipedia.org/wiki/Stochastic_matrix) – Henry Apr 08 '13 at 20:49
  • Thank you, guys. I read the Wikipedia articles but I'm still in the dark. I'm only taking a first course in probability and having completed combinatorial problems, we've just introduced random variables. I wondered if any of you could explain in more detail a solution to the problem. For instance, how probable is to get pattern A before B? How probable is to get pattern A before both B and C? @whuber – superAnnoyingUser Apr 10 '13 at 16:48
  • http://en.wikipedia.org/wiki/Penney%27s_game – whuber Apr 10 '13 at 17:35
  • Henry, did you want to expand on how to turn such questions into a Markov process? – superAnnoyingUser Apr 27 '13 at 10:39
  • @Ivan There are a fixed number of states (if you look at the most recent four or fewer tosses) and a fixed probability of moving from one particular given state to another, so you can construct a transition matrix and treat this as a Markov process with absorbing states. – Henry Jun 23 '13 at 13:01
2

A beatiful formula exists for the case of two words. It was discovered by John Conway and is explained at http://plus.maths.org/content/os/issue55/features/nishiyama/index. I am not aware of any such formula for three or more words. In that case, you may have to find the eigenvalues of the transition matrix as suggested by whuber.

user24831
  • 21
  • 1
1

I think you're going to have to resort to simulation to answer your question. The distribution of the number of tosses until your words occur are complex. For example, even the simple word "HH" has a probability of $1 \over 4$ of occurring in 2 tosses, $1 \over 8$ for 3 tosses, $1 \over 8$ for 4 tosses, and then the probability decreases as the number of tosses increases. [There might be some interest in this simple case for its own right, as the number of combinations that end in a first occurrence of "HH" follow the Fibonacci series as $n$ increases! ]

Anyway, if we let $X$, $Y$, and $Z$ represent the number of tosses until your words A, B, and C are observed, then you are trying to find

$P[X < Min(Y,Z)], P[Y < Min(X,Z),$ and $P[Z < Min(X,Y)]$ .

I am suggesting simulation because no one has been able to supply you a complete answer so far. Note that if you can find two of these probabilities, you know the third.

soakley
  • 4,341
  • 3
  • 16
  • 27