What is the probability of getting TTHH before HHH in repeated fair coin toss? We have a fair coin and it is being tossed until either HHH or TTHH appear. What is the probability of getting TTHH before HHH? I know that the answer is $7/12 \approx 0.583$ but I am not getting why this is the answer. Also, this is counter-intuitive. Shouldn't the probability of getting the pattern HHH be larger than the probability of getting the pattern TTHH since, after four tosses, we can only have one TTHH pattern while we have 3 HHH patterns?
My attempt: I have drawn the probability tree for 4 consecutive coin tosses. Here, we have three patterns (HHHH, HHHT, THHH) that have HHH and one pattern that has TTHH. So, intuitively it should be that the probability of getting TTHH before HHH is less than 1/4 while the probability of getting HHH before TTHH should be 3/4. But this answer is wrong. Correct answer is Pr.(getting TTHH before HHH) = 7/12. I made a python code to estimate this result attached below. It shows the correct answer. But how to make sense of this result? How to get the close form answer of 7/12 without estimating?
Python code for estimating:
import random as rd
cHHH = 0
cTTHH = 0
m = 10000
for i in range(0,m):
  num = str(rd.randint(0,1))
  while ( (num[-4:] != "0011") and (num[-3:] != "111") ):
    num = num + str(rd.randint(0,1))
    if num[-3:] == "111":
      cHHH += 1
      break
    if num[-4:] == "0011":
      cTTHH += 1
      break

p = cTTHH / m
q = cHHH / m
print("Probability of getting TTHH before HHH: ", p)
print("Probability of getting HHH before TTHH: ", q)

#Output: 
Probability of getting TTHH before HHH:  0.5793
Probability of getting HHH before TTHH:  0.4207

 A: I would have guessed that this question is essentially a duplicate, but I wasn't able to find a question with an answer that applies to this particular problem.
We can reformulate this problem using a Markov chain: Explicitly we're looking to compute the probabilities $\Bbb P(HHH), \Bbb P(TTHH)$ that the Markov chain settles into absorbing states corresponding respectively to $HHH$ and $TTHH$ occurring first.
The (eight) states are the possible stages of progress toward one of the two goal sequences ($HHH$, $TTHH$).
The transient states are:

*

*$\emptyset$: the initial state,

*$HT$: sequence ends in $HT$ (includes the sequence $T$)

*$HTH$ (includes $H$, $TH$)

*$TT$

*$HTHH$ (includes $HH$, $THH$)

*$TTH$
The absorbing states are:

*

*$HHH$: sequence ends in the goal $HHH$

*$TTHH$: sequence ends in the goal $TTHH$
In each state transient state there are two possible next states, corresponding to flipping $H$ and $T$ next, respectively, both of which thus have probability $\frac{1}{2}$. Explicitly, the transition matrix of the Markov chain, with respect to the above ordering of states, is
$$
P=\left(
\begin{array}{cccccc|cc}
\cdot & \frac{1}{2} & \frac{1}{2} & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \frac{1}{2} & \frac{1}{2} & \cdot & \cdot & \cdot & \cdot \\
\cdot & \frac{1}{2} & \cdot & \cdot & \frac{1}{2} & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \frac{1}{2} & \cdot & \frac{1}{2} & \cdot & \cdot \\
\cdot & \frac{1}{2} & \cdot & \cdot & \cdot & \cdot & \frac{1}{2} & \cdot \\
\cdot & \frac{1}{2} & \cdot & \cdot & \cdot & \cdot & \cdot & \frac{1}{2} \\
\hline
& & & & & & 1 & \cdot \\
& & & & & & \cdot & 1 \\
\end{array}
\right) .$$
Since the absorbing states are at the end of our list, the above matrix is in a preferred form: The upper-left block, call it $Q$, specifies the transitions between transient states, and the upper-right block, call it $R$, specifies those from transient states to absorbing states.
By construction, if we start in the $i$th transient state the probability of settling in the $j$th absorbing state is the $(i, j)$-entry $B_{ij}$ of $B := N R$, where $N := (I - Q)^{-1}$ is the so-called fundamental matrix of the Markov chain. Since we start in the initial state, $\emptyset$, it's enough to compute $B_{11}$, i.e., the probability that the sequence $HHH$ occurs first, and $B_{12}$, i.e., the probability that $TTHH$ occurs first; since there are only $2$ absorbing states, $B_{12} = 1 - B_{11}$, and so it's enough to compute $$\Bbb P(HHH) = B_{11} = \sum_{k=1}^6 N_{1k} R_{k1} .$$ The only nonzero entry in the first column of $R$ is $R_{51} = \frac{1}{2}$, so $\Bbb P(HHH) = N_{15} R_{51} = \frac{1}{2} N_{15}$, and using Cramer's Rule we can compute $N_{15} = \frac{5}{6}$ without computing the other entries of $N$. Substituting yields the claimed probabilities:
$$\Bbb P(HHH) = \frac{5}{12} \qquad \textrm{and} \qquad \Bbb P(TTHH) = \frac{7}{12} .$$
A: We can imagine infinitely repeating the experiment by flipping an infinite number of coins, parsing the flips into frames of i.i.d. sizes $X_1, X_2, X_3, ...$, where in each frame we imagine "starting over" the experiment, and each frame independently ends with TTHH with probability $p$ and HHH with probability $1-p$.  Let $E[X]=E[X_i]$ for all $i \in \{1, 2, 3, ...\}$.  Then by renewal theory:
\begin{align}
&\frac{p}{E[X]} = (1/2)^4\\
&\frac{(1-p)+(1/2)+(1/2)^2}{E[X]} = (1/2)^3
\end{align}
The left-hand-side of the first equation is the reward per unit time  if we get a reward of 1 for every frame that ends with TTHH.  The right-hand-side of the first equation uses the observation that we can only get TTHH at the end of frames, and the expected number of occurrences of TTHH in $n$ coin flips is exactly $(1/2)^4(n-3)$, so the total reward per unit time must be $(1/2)^4$.
The right-hand-side of the second equation uses the observation that the expected number of occurrences of HHH in $n$ coin flips is exactly $(1/2)^3(n-2)$, so the number of occurrences of HHH per unit time (including those that appear in between frame boundaries) is $(1/2)^3$.   The left-hand-side of the second equation gives a reward at the end of each frame for each occurrence of HHH caused by that frame, where one occurrence is caused if we end with HHH (which happens with probability $1-p$), one "extra" occurrence in between frame boundaries is caused if we flip H after the frame (with prob $1/2$), a final "extra" occurrence in between frame boundaries is caused if we flip HH after the frame (with prob $(1/2)^2$).
Removing $E[X]$ from these two equations gives the equation from my above comment:
$$\boxed{[(1-p)+(1/2)+(1/2)^2](1/p)(1/2)^4 = (1/2)^3 \implies p=7/12}$$
Substituting $p=7/12$ back into the first equation gives
$E[X] = 2^4p = \frac{28}{3}\approx 9.33333$.
A: Here is a partial answer which explains why an apparently counterintuitive  result may be more likely than you first imagine.
If you don't get the pattern HHH in the first three throws or TTHH in the first four, then the first time HHH occurs will either have the last five throws TTHHH or HTHHH, which are clearly equally likely. In the first of these, TTHH wins. And since TTHH can appear without HHH making an appearance, well...
So if you get beyond the fourth throw, TTHH will win more than half of the time.
A: This can be easily done using First Step Analysis
Naming the starting state (before any toss) as $s$,
states for $TTHH$ as $a_1,a_2,a_3,a_4$ respectively,
and states for $HHH$ as $b_1,b_2,b_3$
Tracing movements and writing the equations for the probability that $TTHH$ wins,
$\displaylines{s=\frac12a_1+\frac12b_1\\ a_1=\frac12a_2+\frac12b_1,\quad\quad a_2=\frac12a_2+\frac12a_3,\quad\quad a_3=\frac12*1+\frac12a_1,\\ b_1=\frac12b_2+\frac12a_1,\quad\quad b_2=\frac12*0+\frac12a_1}$
This yields the probability that $TTHH$ wins, $s = \dfrac7{12}$
A: Here's an outline for solving this problem exactly:

*

*Formulate the problem as a Markov chain. You will have one state for each word over T, H which is a prefix of either HHH or TTHH (including the empty word, which stands for the initial state), for a total of 8 states. The two final states will have a probability $1$ loop, as the system never leaves those states. For all other states, you will have exactly two possible transitions, each with probability $1/2$, depending on the result of the next flip.

*Put the transition table of the Markov chain in matrix form $M$ so that given a vector $v$ of probabilities of being in each of the $8$ states, $M \cdot v$ will tell you the probabilities after one more flip.

*Take $v_0$ as the unit vector with a $1$ on the position corresponding to the initial state and $0$ elsewhere. With this, $M^n \cdot v_0$ will give you the probabilities after $n$ flips. Compute this value for a few small values of $n$ (preferably put this in Python to avoid mistakes; you can also factor out $1/2$, the rest will be only integers and you don't have to worry about precision). From that, guess the formula for $M^n \cdot v_0$ in terms of $n$ and prove it by induction.

*Compute the limit $lim_{n \to \infty} M^n \cdot v_0$. This will hold the answer to your problem. For verification, the limit should have probability $0$ for all non-final states.

