Fair coins are tossed and when either four consecutive heads and tails appear the process will be stopped. What is the probability of two consecutive head or tail or any one of them in a row?
[Math] Probability of two consecutive head or tail or any one of them in a row
combinatoricsprobability
Related Solutions
Let $X$ be the random variable that counts the number of tosses until we get two successive tosses of the same type. Although you did not say so explicitly, I assume that you want the probability mass function of $X$.
What is the probability that $X>n-1$? We need to have a sequence of tosses of length $n-1$ and of type HTHTHT and so on (alternating heads and tails, starting with head), or THTHTH and so on. The probability that the first type of sequence is followed up to and including the $(n-1)$-th toss is $\frac{1}{2^{n-1}}$. The second type of sequence has the same probability, for a total of $\frac{2}{2^{n-1}}$.
The number $X$ of tosses is equal to $n$ if $X>n-1$ and the last toss matches the next to last toss. The probability of that is $\frac{1}{2}$, so $$P(X=n) =\frac{2}{2^{n-1}}\cdot\frac{1}{2}.$$ This simplifies to $\dfrac{1}{2^{n-1}}$. Note that $n$ ranges over the integers that are $\ge 2$.
Another way: The first toss doesn't matter. After that, it is just a matter of matching the previous toss. So it is very much like tossing a fair coin and winning if you get (say) heads. The only difference is the "wasted" toss at the beginning. If we are tossing a fair coin, and $Y$ is the number of tosses until the first head, then $P(Y=n)=\frac{1}{2^n}$ ($n=1, 2, \dots$). But $X$ has the same distribution as $Y+1$. So $P(X=n+1)=P(Y=n)=\frac{1}{2^n}$, or equivalently $$P(X=n)=P(Y=n-1)=\frac{1}{2^{n-1}}\quad (n=2,3,\dots).$$
Generalization: Suppose that the probability of a head is $p$, and the probability of a tail is $q=1-p$. Either analysis of the problem can be extended to the more general situation. We win on the $n$-th toss if we did not win on the first $n-1$, and then the $n$-th toss matches the previous one.
It is convenient to split the analysis into two cases, $n$ odd and $n$ even. We do a full analysis of the odd case. So let $n=2m$. As is the first analysis, there are two ways to win on the $(2m+1)$-th toss. Either (i) we went HTHTHT and so on, with a tail on the $(2m)$-th toss, and then a tail again on the $(2m+1)$-th toss, or (ii) we went THTHTH and so on, with a head on the $(2m)$-th toss, and a head again on the $(2m+1)$-th toss.
The probability of (i) is $p^mq^m q$ and the probability of (ii) is $q^mp^mp$. Add them together. We get $p^mq^m(p+q)$, which is $p^mq^m$ ($m=1,2,\dots)$.
Next we deal with the case $n$ is even, say $n=2m$. The calculation is very similar to the previous one, so it will be omitted. The probability is the slightly more complicated-looking $p^mq^{m-1}p+q^mp^{m-1}q=p^{m-1}q^{m-1}(p^2+q^2)$, where $m$ ranges over the positive integers.
We deal with the general case of $n\ge 2$ coins.
Let the $i$-th coin have probability $p_i$ of landing heads, and $q_i$ of landing tails. (Of course $p_i+q_i=1$, but that will turn out to be of no importance!)
Then the probability of $k$ heads and $n-k$ tails is the coefficient of $x^k$ in the product $$(p_1x+q_1)(p_2x+q_2)(p_3x+q_3)\cdots(p_nx+q_n).$$ If the probabilities are to be all equal, this product must be identically equal to $$\frac{1}{n+1}(x^n+x^{n-1}+x^{n-2}+\cdots +x+1).$$ However, $x^n+x^{n-1}+x^{n-2}+\cdots+x+1=0$ has some non-real roots, and therefore cannot be expressed as a product of $n$ linear factors with real coefficients.
Remark: Though we did not use the term, this was a generating function argument. Note how smoothly a generating function argument can sidestep potentially messy algebra.
Best Answer
Because heads and tails play symmetric roles in the stopping criterion (and presumably have equal chances in each Bernoulli trial), it suffices to find the probability of getting two consecutive heads before the process stops.
If the process stops with four consecutive heads, obviously that means also we got two consecutive heads before the process stops. So we can focus on the probability $p$ that we get two consecutive heads before the process stops with four consecutive tails.
One way to compute this is by defining a Markov chain with two absorbing states, a) two consecutive heads and b) four consecutive tails. Finding $p$ amounts to finding the probability of reaching the first of these absorbing states (two consecutive heads).
The Wikipedia write-up of absorbing Markov chains may be overly concise, so here are some details. Ordering the transient states before the absorbing states gives a probability transition matrix having block structure:
$$ P = \begin{bmatrix} Q & R \\ 0 & I \end{bmatrix}$$
so that $Q$ gives the transition probabilities between the transient states and $R$ the transition probabilities from transient to absorbing states.
We define the fundamental matrix $N = \sum_{k=0}^\infty Q^k = (I-Q)^{-1}$, and the product $NR$ then gives the probabilities of eventually reaching an absorbing state starting from a transient state.
In the case at hand it is convenient to use four transient states (consecutive runs of one Head or of one to three Tails, resp.) and two absorbing states (two consecutive Heads or four consecutive Tails). Taking the states in just this order gives:
$$ P = \begin{bmatrix} 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$
$$ N = (I-Q)^{-1} = \begin{bmatrix} \frac{16}{9} & \frac{8}{9} & \frac{4}{9} & \frac{2}{9} \\ \frac{14}{9} & \frac{16}{9} & \frac{8}{9} & \frac{4}{9} \\ \frac{4}{3} & \frac{2}{3} & \frac{4}{3} & \frac{2}{3} \\ \frac{8}{9} & \frac{4}{9} & \frac{2}{9} & \frac{10}{9} \end{bmatrix} $$
$$ NR = \begin{bmatrix} \frac{8}{9} & \frac{1}{9} \\ \frac{7}{9} & \frac{2}{9} \\ \frac{2}{3} & \frac{1}{3} \\ \frac{4}{9} & \frac{5}{9} \end{bmatrix} $$
For economy I omitted an "empty" state, so we imagine our Markov process to initialize in state one Head with probability $1/2$ and likewise in state one Tail with probability $1/2$. From the above computation it follows that our chance of reaching two consecutive Heads before four consecutive Tails is:
$$ (1/2)\frac{8}{9} + (1/2)\frac{7}{9} = \frac{5}{6} $$
This is the same as our chance of reaching two consecutive Tails before four consecutive Heads.