Cup Swap

My friend has three cups, labeled “A,” “B,” and “C” in a row. She picks two random cups and swaps their position. Then she does this again and again, picking a random pair each time, until all three cups are back in their original order. For example, here is one such sequence of swaps:

• A, B, C (original)
• C, B, A (first and third were swapped)
• B, C, A (first and second were swapped)
• B, A, C (second and third were swapped)
• A, B, C (first and second were swapped)

In this example, the cups returned to their original order after four swaps. On average, how many swaps would you expect until the cups return to their original order?

There are six possible states for the cups: ABC, ACB, BAC, BCA, CAB, and CBA. If we initially set up a Markov chain, with the assumption that each choice of two cups to switch are equally likely, we get the transition matrix $$M = \begin{pmatrix} 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \\ 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \end{pmatrix}.$$ Playing around on with the transition matrix, we see that if we start at ABC, then after an even number of swaps the state can be any one of ABC, BCA or CAB, while after an odd number of swaps the state can be any one of ACB, BAC or CBA. In order to solve this particular problem, let's separate ABC from the other states BCA and CAB. Let's say that we have new states $ABC,$ $X = \{ BCA, CAB \}$ and $Y = \{ACB, BAC, CBA\}.$ In this reduced Markov chain state we see that if you are at $ABC$ then almost surely you end up at $Y$ after a swap; if you are at $X$ then almost surely you end up at $Y$ after a swap; and if you are at $Y$ then with probability 1/3 you end up at $ABC$ and with probability 2/3 you end up at $X$.

Therefore, we see that if $2n$ is the first number of swaps that return you to ABC, then since there needs to be at least one swap from $Y$ to $ABC$, then we must have $(n-1)$ loops from $Y$ to $X.$ Therefore, $$p_n = \mathbb{P} \{ 2n \text{ swaps to first return to ABC } \} = \frac{1}{3} \left( \frac{2}{3} \right)^{n-1},$$ so the expected number of swaps needed to return to ABC is $$E = \sum_{n=1}^\infty 2n p_n = \frac{2}{3} \sum_{n=1}^\infty n \left(\frac{2}{3} \right)^{n-1} = \frac{2}{3} \left( \frac{1}{1-2/3} \right)^2 = 6.$$