Posted on Sep 18, 2026
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 arrangements of the three cups. At each step, we choose one of the three possible pairs of positions and swap them.
One way to solve the problem is to use the symmetry of these six arrangements. The process is a random walk on the six possible permutations of \(A,B,C\). From any arrangement, there are exactly three possible next arrangements, each equally likely.
Because the random walk is symmetric, in the long run it spends the same fraction of time at each of the six arrangements. So the stationary probability of being at the original arrangement \(ABC\) is
\[ \pi(ABC)=\frac{1}{6}. \]
For a finite Markov chain, the expected return time to a state is the reciprocal of its stationary probability. Therefore, the expected number of swaps until returning to \(ABC\) is
\[ \frac{1}{\pi(ABC)}=6. \]
Answer: \( \boxed{6} \) swaps.
We can also check this with a direct equation. After one swap, the cups are certainly not in the original order. Let \(x\) be the expected additional number of swaps to return to \(ABC\) from any non-original arrangement.
The six arrangements split into two types: the original arrangement, and the five others. But among the five others, not all are the same distance from \(ABC\). A cleaner version is to track whether the current arrangement has even or odd parity.
Every swap changes parity. The original arrangement \(ABC\) is even. So the process can only return to \(ABC\) after an even number of swaps. The random walk alternates between the three even arrangements and the three odd arrangements.
From any odd arrangement, one of the three swaps returns to \(ABC\), while the other two go to the other two even arrangements. Solving the corresponding small system again gives expected return time \(6\), matching the symmetry argument above.
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?
Now this is a cover time problem: starting from \(ABC\), how long does it take until we have visited all six arrangements?
The key observation is that the six arrangements form the complete bipartite graph \(K_{3,3}\). The three even permutations are on one side, and the three odd permutations are on the other. Each swap changes parity, so every move crosses from one side to the other.
Let
\[ E_{e,o} \]
be the expected number of additional swaps needed to see all six arrangements, given that we are currently at an even arrangement, have already seen \(e\) of the three even arrangements, and have already seen \(o\) of the three odd arrangements.
Similarly, let
\[ O_{e,o} \]
be the corresponding expectation when we are currently at an odd arrangement.
From an even arrangement, the next move goes to one of the three odd arrangements. If \(o\) odd arrangements have already been seen, then with probability \(o/3\) we revisit an old odd arrangement, and with probability \((3-o)/3\) we discover a new one. Thus
\[ E_{e,o} = 1+\frac{o}{3}O_{e,o} +\frac{3-o}{3}O_{e,o+1}. \]
Similarly, from an odd arrangement,
\[ O_{e,o} = 1+\frac{e}{3}E_{e,o} +\frac{3-e}{3}E_{e+1,o}. \]
The boundary condition is
\[ E_{3,3}=O_{3,3}=0, \]
since once all six arrangements have been visited, there is nothing left to do.
Working backward through these equations gives the following useful values:
| State | Expected remaining swaps |
|---|---|
| \(E_{3,2}\) | \(5\) |
| \(O_{2,3}\) | \(5\) |
| \(E_{2,2}=O_{2,2}\) | \(8\) |
| \(E_{2,1}=O_{1,2}\) | \(\frac{68}{7}\) |
| \(E_{1,1}=O_{1,1}\) | \(\frac{157}{14}\) |
We start at \(ABC\), which is an even arrangement. We have seen one even arrangement and zero odd arrangements. The first swap must take us to a new odd arrangement, so
\[ E_{1,0}=1+O_{1,1}. \]
Since
\[ O_{1,1}=\frac{157}{14}, \]
we get
\[ E_{1,0}=1+\frac{157}{14} = \frac{171}{14}. \]
Extra credit answer: \( \boxed{\frac{171}{14}} \), or approximately \( \boxed{12.214} \), swaps.
So the expected time to return to the original order is exactly \(6\) swaps, while the expected time to see every possible order is a little more than \(12\) swaps.
The average is \(6\), but the whole distribution of the return time is available in closed form, and it is worth having because it gives the simulation below something sharp to check against.
Collapse the six arrangements into three classes: home (\(ABC\)), the two other even arrangements, and the three odd arrangements. From home, every swap lands on an odd arrangement. From an odd arrangement, exactly one of the three swaps goes home and the other two go to a non-home even arrangement. From a non-home even arrangement, all three swaps lead to odd arrangements, so home is never reachable in one step.
The walk therefore visits an odd arrangement at swaps \(1, 3, 5, \dots\), and at each of those visits it goes home on the next swap with probability \(1/3\), independently of the past. So \(T/2\) is geometric with success probability \(1/3\):
\[ P(T=2k)=\frac{1}{3}\left(\frac{2}{3}\right)^{k-1}, \qquad k=1,2,3,\dots \]
which confirms \(\mathbb{E}[T]=2\cdot 3=6\). Note that the median is only \(4\) swaps: the mean is dragged upward by a long tail.
The six arrangements sit on the complete bipartite graph \(K_{3,3}\), with the three even arrangements on the left and the three odd ones on the right. Every swap follows one edge, which is why the walk strictly alternates sides. Step through it by hand, or let it run until both milestones are hit.
current already visited not yet visited home (\(ABC\))
The symmetry argument claims the walk spends \(1/6\) of its time at each arrangement. This chart tracks the share of visits so far in the walk above, so fast-forwarding a few thousand swaps should flatten all six bars toward the dashed line at \(1/6\). The expected return time of \(6\) is just the reciprocal of that height.
Each trial runs a fresh sequence of random swaps and records two things: the first swap at which the cups are back in their original order, and the first swap at which every arrangement has been seen. The number of cups is adjustable, which is a way to test the generalization below.
The symmetry argument never used the number three. With \(n\) cups, a swap picks one of the \(\binom{n}{2}\) pairs of positions, so the walk lives on a connected, regular graph whose vertices are the \(n!\) arrangements. A regular graph has a uniform stationary distribution, so \(\pi=1/n!\) and
\[ \mathbb{E}[\text{swaps to return}]=n!. \]
That is \(6\) for three cups, \(24\) for four, and \(120\) for five, all of which the simulator above reproduces. The cover time has no comparably tidy closed form once \(n>3\), so for four and five cups the simulator reports the empirical value only; it climbs to roughly \(96\) swaps for four cups and \(713\) for five.
More Fiddlers: Previous | Next