Dice waiting time for $5,6$ is smaller than for $6,6$? (I have also posted this on MO) 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 and I must admit the result is intuitively not too obvious to me. The fast way to convince me that the problem is correct is by simulation, so I'd like to gain new perspectives in order to adjust my intuition. 
What I'm asking is whether you can provide me with some solution which is (ideally) both rigorous and intuitive. That being said, any light shed on the subject is very much appreciated. Also, in what way can that solution 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: In the first case you roll the die until you have a five, then if the next die is not a six it might be a five.
$$\mathsf E(\tau_{56}) = \mathsf E(\tau_5)+\mathsf E(\tau_{56}\mid h_5) \\ \mathsf E(\tau_{56}\mid h_5) = \tfrac 16+\tfrac 46\mathsf E(\tau_{56})+\tfrac 16\mathsf E(\tau_{56}\mid h_5)$$
In the second case, you roll the die until you have a six.  If the next die is not a six it can't be a six.
$$\mathsf E(\tau_{66}) = \mathsf E(\tau_6)+\mathsf E(\tau_{66}\mid h_6) \\ \mathsf E(\tau_{66}\mid h_6) = \tfrac 16+\tfrac 56\mathsf E(\tau_{66})$$
So the intuition is that in the first case you may have a second chance at getting a six followed by a five if you get a five followed by a five.
A: Here is an intuition that can, with a bit of work, be turned into a rigorous proof.
Imagine rolling the die $36N+1$ times, where $N$ is a huge number.  If you look at any random pair of consecutive rolls, you can expect to see any of the $36$ possibilities with equal probability.  So you can expect to see the consecutive pair $56$ roughly $N$ times, and the same for $66$.
Now imagine snipping your list of $36N+1$ rolls into pieces that end with a $56$, tossing away the end of the list after the last $56$.  You expect to have $N$ pieces, of average length (in the limit) $36$.
Now imagine snipping your list into pieces ending with a $66$ (again tossing away the end after the final snip).  It might seem this should give the same answer as before, but it doesn't.  This is because you only snip once when you encounter a string of three consecutive $6$'s, not twice.  Each time you snip, there is a $1\over6$ chance that the next roll is another $6$, so the number of occurences of $66$ is roughly the number of snips plus one-sixth of the number of snips, which means the number of snips is roughly six-sevenths of the number of occurences of $66$, or ${6\over7}N$, and this means the average length of the snipped pieces (again, in the limit) is $42$.
