Flip a fair coin until three consecutive heads or tails appear What is the expected number of flips until three consecutive heads or tails appear?
 A: This can be seen as an MC with 4 states. Denote for convenience $S=\{HHH, TTT\}$ 
One thing to notice first, is that only before you have tossed any coins at all you need 3 matching tosses till $S$. After that, regardless of the outcome, you have no more than two matching tosses from $S$. Hence we have the following MC:
$S_0$: 3 matching tosses till $S$
$S_1$: 2 matching tosses till $S$ 
$S_2$: 1 matching tosses till $S$ 
$S_3$: 0 matching tosses till $S$ 
Denoting $m_{i,j}$ the mean hitting time of state $j$ starting in state $i$, we obtain the following set of recurrent equations:
$$
m_{0,3}=1+m_{1,3}\\
m_{1,3}=1+0.5 m_{1,3} +0.5m_{2,3}\\
m_{2,3}=1+0.5 m_{1,3} +0.5m_{3,3}
$$ 
And the boundary condition is of course $m_{3,3}=0$. Solving this set of equations we get
$$
m_{0,3}=1+6=7
$$
A: Let $P$ be the expected number when the last two flips match, $Q$ the expected number when the last two flips don't match (or there has only been one flip).  Our answer is $Q+1$ as the first flip will take us to state $Q$.
Then $P=\frac 12 \text{(that we match the last 2)}+\frac 12 (Q+1)\text{ (as we are now in state } Q)$
$Q=\frac 12 (1+P)\text{(that we match the last flip)} + \frac 12 (1+Q)\text{(that we don't match the last flip)}$
This gives $P=4, Q=6$ and our final answer is $7$
A: Here is probably another way and hope this can be easier to understand.
Let us assume to get HHH for X number of times, then for {HHH, TTT} is just X/2.
1)first time get T, then just waste one time, everything turns to be same as before, plus this event chance is 1/2. Then to get HHH is 1/2*(X+1)
2)first time get H
2.1)second time get T, then waste two times plus 1/4 probability of this event. Then total number is 1/4*(X+2)
2.2)second time get H
2.2.1) third time get T, then waste 3 times plus 1/8 prob of this event. Then total number is 1/8*(X+3)
2.2.2) third time get H, this is perfect and prob is 1/8. So total number is 1/8*3.
Now, everything sum together should converge to X.
we have:
1/2*(X+1) + 1/4*(X+2) + 1/8*(X+3) + 1/8*3 = X
=> X = 14.
So to get {HHH, TTT} is X/2 = 7.
A: I think it should be 14.
$X_k$=number of flips needed to obtain first k consecutive heads.
$$E[X_k]=\frac{1}{p}+\frac{1}{p*2}+\cdots+\frac{1}{p*k}$$
where
 $$p(\text{Heads})=p \\
      p(\text{Tails})=1-p$$
and p is not equal to zero.
A: Let us keep it general and assume that $\mathrm{P(heads})=p$ and $\mathrm{P(tails})=1-p=q$, and start by analyzing only the event of three consecutive heads, which composes the larger event asked. 
All sequences can be obtained by appending to the initial sequences {T,HT,HHT,HHH}, the last one already having our target event. So, these sequences induce a partition of the sample space. Furthermore, every time a T appears, the subsequent sequences will also be generated by these initial sequences, thus they induce also a partition of the sub-events, being recurrent. So, it is possible to express the probability $f(k)$ of three consecutive tails occurring after $k$ flippings, conditionally on those sequences:
\begin{equation}
\begin{array}{ll}
f(k)=0,  & k<3\\
f(3)=p^3 \\
f(k)=qf(k-1)+pqf(k-2)+p^2qf(k-3), & k >3; 
\end{array}
\end{equation}
where the interpretation of the recurrence equation is that each of its terms corresponds to each of the sequences {T,HT,HHT} occurring before the sub-events become a copy of the same recurrence relation.    
If one prefers to interpret the flipping sequences being generated by transitions in a Markov Chain (MC), all transitions associated to the occurrence of a T point to the same state, which will need at least three more flippings to obtain the desired event. The states can be expressed as {{},H,HH,HHH}, each of these labels expressing uninterrupted sequences of heads in the last three flippings. Every time a T occurs, the system returns to the state {}. The state HHH is terminal. Then, the recurrence relation $f(k)$ above expressed can be obtained by analyzing the probabilities of trajectories in the MC.
Given that the expected number of flips (the expectation of the random variable $K_{3\mathrm{T}}$) until three consecutive heads appear can be expressed as $\mu=E(K_{3\mathrm{T}})=\sum_{k=1}^{\infty}kf(k)$, we apply this summation to the definition of $f(k)$ above and manipulate as following:
\begin{equation}
\mu=\sum_{k=1}^{\infty}kf(k)=3f(3)+\sum_{k=4}^{\infty}k\left[qf(k-1)+pqf(k-2)+p^2qf(k-3)\right]\\
=3p^3+q\sum_{k=4}^{\infty}kf(k-1)+pq\sum_{k=4}^{\infty}kf(k-2)+p^2q\sum_{k=4}^{\infty}kf(k-3),
\end{equation}
from which we can deduce that
\begin{equation}
\begin{array}{lll}
\sum_{k=4}^{\infty}kf(k-1)=&4f(3)&[=f(3)+3f(3)]\\
& +5f(4)&[=f(4)+4f(4)]\\
& ...\\
& +(1+n)f(n)&[=f(n)+nf(n)]\\
&=\\
&1+\mu&[=\sum_{k=3}^{\infty}f(k)+\sum_{k=3}^{\infty}kf(k)].
\end{array}
\end{equation}
Applying the same reasoning for the other summations, we conclude that
\begin{equation}
\mu=q(1+\mu)+pq(2+\mu)+p^2q(3+\mu)+3p^3,
\end{equation}
from which we can use that $q=1-p$ and isolate $\mu$ such that
\begin{equation}
\mu=p^{-3}(1+p+p^2).
\end{equation}
The event of three consecutive tails is symmetric to three consecutive heads, so $\lambda=E(K_{3\mathrm{H}})=q^{-3}(1+q+q^2)$. If $p=q=1/2$, we have $\lambda=\mu=14$ and, with certain assumptions (e.g. independence, type of distribution), we could argue that the average time for either event occur is half of this time. However I am not sure about what assumptions would be needed and how they could be checked, so I will restart the demonstration from scratch using arguments similar to the ones used above.
A MC which generates the sequences until three consecutive heads or tails occur, for $p\in[0,1]$, has the following states: {{},H,HH,HHH,T,TT,TTT}, where {} occurs only at the beginning, and HHH and TTT are terminal or absorbing. The problem of establishing a recurrence relation from this MC is that it does not have a single state to which all of the non-absorbing states may return, as it happened for the example given above. However, we can consider the following two mutually exclusive events: the initial transition goes to H and the initial transition goes to T. This allows us to express the probability mass function $g(k)$ as:
\begin{equation}
g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T}),
\end{equation}
which is conditioned on either H or T occurring first. The MC associated to $g(k|\mathrm{H})$ has all the states of that associated to $g(k)$ except {}, and starts at the state H; similarly to that associated to $g(k|\mathrm{T})$, which starts at T. With each of these MCs, it is possible to find a recurrence relation. 
Let us start by analyzing $g(k|\mathrm{T})$. In order to express its recurrence relation, we have to identify all possible trajectories which either terminate or return to the initial state T. These are 
 {TTT,TTHT,TTHHT,TTHHH,THT,THHT,THHH}. They are used to identify the event partitions below:
\begin{equation}
\begin{array}{rlll}
g(k|T)=&       &=0,              & k<3\\
g(3|T)=&\mathrm{P}(\mathrm{TTT})      &=q^2, \\
g(4|T)=&\mathrm{P}(\mathrm{THHH})      &=p^3,\\
g(5|T)=&\mathrm{P}(\mathrm{TTHHH})+\mathrm{P}(\mathrm{THT})g(3|\mathrm{T})&=p^3q+pq^3, \\
g(k|T)=&\mathrm{P}(\mathrm{TTHT})g(k-3|\mathrm{T})+\mathrm{P}(\mathrm{TTHHT})g(k-4|\mathrm{T})\\
&+\mathrm{P}(\mathrm{THT})g(k-2|\mathrm{T})+\mathrm{P}(\mathrm{THHT})g(k-3|\mathrm{T}) \\
=&pq.g(k-2|\mathrm{T})+(p^2q+pq^2)g(k-3|\mathrm{T})\\
&+p^2q^2.g(k-4|\mathrm{T}),& & k\geq 6.
\end{array}
\end{equation}
Similarly to what I did for $f(k)$ above, I use the expectation formula $\mu_T=E(K_3|T)=\sum_{k=1}^{\infty}k.g(k|\mathrm{T})$ to obtain
\begin{equation}
\mu_t=3q^2+4p^3+5p^3q+pq(\mu_\mathrm{T}+2)+(p^2q+pq^2)(\mu_\mathrm{T}+3)+p^2q^2(\mu_\mathrm{T}+4)
\end{equation}
and, making $\mu_T$ explicit:
\begin{equation}
\mu_T=\frac{p^4-p^3-2p^2+p-3}{p^4-2p^3-p^2+2p-1}.
\end{equation}
In which the denominator never vanishes for $p\in[0,1]$. Because the problem structure is symmetric for $g(k|\mathrm{H})$, we can obtain $\mu_H=E(K_3|\mathrm{H})$ by substituting $q$ for $p$ in the formula above. And, from the fact that $g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T})$, we can deduce that
\begin{equation}
E(K_3)=p.E(K_3|\mathrm{H})+q.E(K_3|\mathrm{T})=p\mu_\mathrm{H}+q\mu_\mathrm{T}.
\end{equation}
We can easily verify that a fair coin gives $E(K_3)=7$.
A: The expected number of flips until you get TWO consecutive heads or tails is three which is fairly easy to calculate: Let $N$ denote the number of throws then the last two throws must be either $HH$ or $TT$ with the remaining sequence exactly determined as $...HTHTHH$ or $...THTHTT$. Therefore, $P(N)=0.5^{N-1}, N=2,3,...$ with $\langle N\rangle=3$. Because of the symmetry, the average number is $6$ for getting $HH$ and the same for $TT$.
Now for THREE consecutive heads or tails, let's throw the first time: $i$) if it's $H$ with the probability of $\frac{1}{2}$, then you need to additionally throw on average $6$ times to get $HH$ $ii$) if you get T with the probability of $\frac{1}{2}$, then another 6 throws on average for TT. Finally, $\frac{1}{2}(6+1)+\frac{1}{2}(6+1)=7$
