Can You Swap The Cups?¶
Fiddler¶
My friend has three cups, labeled “A,” “B,” and “C” in a row. She randomly picks two different cups and swaps their positions. 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?
WLOG, assume the original order is A, B, C, from Group I.
- Any swap will lead to a permutation from \Group II.
- Any swap from Group II has a $\dfrac{1}{3}$ chance of swapping back to A, B, C and a $\dfrac{2}{3}$ chance of the other two permutations in Group I.
This leads to the following transition diagram :
This yields the following equations :
\begin{align*} EV_{IS} \text{ } =& \text{ } 1 + \dfrac{1}{3}EV_{GII} \\\\ EV_{GI} \text{ } =& \text{ } 1 + \dfrac{2}{3}EV_{GII} \\\\ EV_{GII} \text{ } =& \text{ } 1 + EV_{GI}\\ \end{align*}
Answer¶
Solving yields
\begin{align*} EV_{IS} \text{ } =& \text{ } 3 \\\\ EV_{GI} \text{ } =& \text{ } 5 \\\\ EV_{GII} \text{ } =& \text{ } 6\\ \end{align*}
Extra Credit¶
In total, there are six possible orders of the cups. Without any swaps, one of those orders (A, B, C) has already been achieved.
On average, how many swaps would you expect until the remaining five orders (and thus, all six) are also achieved?
Solution¶
I ran $100,000,000$ trials and achieved
Answer¶
$$\boxed{\approx 12.21}$$