Dice waiting time for $5,6$ is smaller than for $6,6$ I've asked this in MSE, but maybe it actually belongs here.:
So I've had this problem in the back of my mind for a while. I recall having seen a rigorous  solution using some advanced probability theory, but I've lost the reference.
What I'm asking is whether you can provide me with some solution which is (ideally) both rigorous and intuitive. Also, maybe even more relevant is whether that solution can be generalised to a more general setup?
Problem: 
Consider an iid sequence $(X_n)_{n\in\mathbb{N}}$ corresponding to independent tossing of a fair die. Define 
$$\tau_{5,6}=\inf\{n\in\mathbb{N}:X_n=5,X_{n+1}=6\}, \:\:\:\tau_{6,6}=\inf\{n\in\mathbb{N}:X_n=6,X_{n+1}=6\}.$$
Then $E\tau_{5,6}<E\tau_{6,6}$. 
Extension: Actually $E\tau_{5,6}=36$ while $E\tau_{6,6}=42$.
 A: Compare 56 and 55 instead. Denote $a=6$ in the first case and $a=5$ in the second, $b=11-a$. Look at the first 5. If the next term equals $a$, we are done (the same thing for both cases). If the next term is 1,2,3 or 4, we have to start from the beginnng (in both cases). But what if the next term is $b$? For 55 we again start from the beginning, but for 56 this $b=5$ may be useful. Thus for 56 we wait less in average.
A: Here is a completely elementary argument.
Let $T_{56}:=\tau_{56}+1, T_{66}:=\tau_{66}+1$  be the first times
the patterns have appeared, i.e.
$$T_{56}:=\inf\{ n \geq 2\;:\;X_{n-1}=5,\,X_n=6 \}$$ etc. It is easy to see
that $T_{56}$,$T_{66}$ have moments of all orders.
Let $p_5,p_6$ be the probabilities for $5$ resp. $6$ and let  $k\geq 2$. Consider the outcomes
for which the pattern has not appeared until $k-2$ and shows up in $(X_{k-1},X_k)$.
For the pattern $56$ we get
\begin{align*}p_5\,p_6\,\mathbb{P}(T_{56}>k-2)&=\mathbb{P}(T_{56}>k-2,\,X_{k-1}=5,\,X_k=6)\\
                                              &=\mathbb{P}(T_{56}=k-1,\,X_{k-1}=5,\,X_k=6)+\mathbb{P}(T_{56}=k,\,X_{k-1}=5,\,X_k=6)\\
                                              &=\mathbb{P}(T_{56}=k)\end{align*}
Summing over $k\geq 2$ gives $p_5p_6\,\mathbb{E}(T_{56})=1$.
For the pattern $66$ we get
\begin{align*}p_6^2\,\mathbb{P}(T_{66}>k-2)&=\mathbb{P}(T_{66}>k-2,\,X_{k-1}=6,\,X_k=6)\\
                                              &=\mathbb{P}(T_{66}=k-1,\,X_{k-1}=6,\,X_k=6)+\mathbb{P}(T_{66}=k,\,X_{k-1}=6,\,X_k=6)\\
                                              &=\mathbb{P}(T_{66}=k)+ p_6\,\mathbb{P}(T_{66}=k-1)\end{align*}
Summing over $k\geq 2$ gives $p_6^2\,\mathbb{E}(T_{66})=1+ p_6$.
Compared to the above, the rhs has an additional term because it is possible that the pattern has been completed at a position inside  the final pattern.
If $p_5=p_6$ the expectation of $T_{66}$ is therefore larger than that of $T_{56}$.
Clearly general patterns can be treated similarly.
