You're trying to get a cat, a fish, a dog, and your lunch across a river, but there's a troll in the way. The troll says, "I'll allow you to cross the river, but only if you play this game with me. I have a die here showing a cat, a fish, a dog, and your lunch. I'll roll that die, and then you must bring that item across the river, no matter which side it's on. Once you do that, I'll roll the die again. If you can get everything to the other side, I'll let you go."
You quickly realize this is a bad idea: If you leave the cat and fish alone on one side, the cat will eat the fish, and if you leave the dog and lunch alone on one side, the dog will eat your lunch. (If the cat, the fish, and something else are alone on one side, nothing will be eaten. Likewise, if the dog, your lunch, and something else are alone on one side, nothing will be eaten.) You tell this to the troll, who says, "Fine. When I absolutely need to, I'll re-roll the die to make sure none of your precious cargo is harmed."
Suppose that you make a move when you bring something from one side of the river to the other. (If the troll re-rolls their die, this does not count as a move.) Find the expected number of moves you'll need to make before everything is on the other side of the river.
I honestly don't know where to start with this problem and a solution would be greatly appreciated.
We can map this to a Markov chain on $\{0,1,2,3,4\}$, with the states representing the number of items that have been brought across the river. The transition probabilities are: $0$ and $4$ always transition to $1$ and $3$, respectively; $1$ and $3$ transition to $0$ and $4$, respectively, with probability $\frac13$ and to $2$ with probability $\frac23$ (since the fourth option causes a re-roll), and $2$ transitions to $1$ or $3$ with equal probability $\frac12$.
It takes $E_0=1$ move to get from $0$ to $1$.
Then it takes $E_1$ moves to get from $1$ to $2$, with
$$ E_1=1+\frac13(E_0+E_1)\;, $$
with solution $E_1=2$.
Then it takes $E_2$ moves to get from $2$ to $3$, with
$$ E_2=1+\frac12(E_1+E_2)\;, $$
with solution $E_2=4$.
And then it takes $E_3$ moves to get from $3$ to $4$, with
$$ E_3=1+\frac23(E_2+E_3)\;, $$
with solution $E_3=11$.
Thus in total the operation is expected to take $1+2+4+11=18$ moves.