Misplaced Priorities - Part 3 [Solution]

Solution for the week of 1/19/25

Our problem from 1/19/25 was

Our job is to figure out how many swaps on average are needed to order a line of 10 people that have been shuffled randomly where before each one of your swaps, a random swap will occur. Once you’ve successfully re-ordered the line of 10 people, the random swaps will stop (so the situation doesn’t go on indefinitely). How many swaps on average for a line of n people?

I ended up finding the problem really fun and challenging! To start we should recall that to “fix” a line, we needed to perform n-c=s swaps where n is the number of people in line and c is the number of cycles in the permutation if we think of the current order of the line as a permutation of the correct order. Now however, we have a random swap that occurs. This could potentially modify the existing cycle structure we have and, in fact, is actually guaranteed to change the cycle structure as we will see. So we must consider (1) how such swaps change the cycles structure and (2) the probability of such cycle structure change.

Starting with how the swaps change the cycle structure, we first consider the random swaps. As it turns out (proofs are provided in the full write up here), each random swap must either merge a cycle if the two selected elements are part of different cycles or break up a cycle if the two selected elements are part of the same cycle. For the swap we select, we effectively want every element into a 1-cycle with itself (the identity permutation) so we will always want to break up cycles. But which cycle should we break up? At first it might seem that it doesn’t matter—they all need to be broken up anyway and any given break reduces the number of remaining swap by the same amount anyway, namely 1. However, once we consider the random swap that will follow our decision, we will recognize that selecting the smallest cycles to break up results in a greater probability that the random swap will also create a break. This is also proven in the full writeup.

Now, we need to consider the probabilities of the cycles structure changes discussed above. Starting simple, the intentional swap will always result in the breaking of the smallest cycle of size greater than 1 (ties can be broken arbitrarily). For the random swap, we must consider the case where cycles are joined and broken. In the case where a cycle is broken, We can think of breaking a cycle of size c into two cycles of size i and c-i. In terms of selecting two elements from the cycle that accomplish this, there are generally c different possible ways of selecting two elements in a cycle such that they are exactly i places apart with one notable exception. If you have an even number of elements in the cycle then if i = c/2, the element orientation becomes arbitrary so there are only c/2 unique pairings that result in an even cycle split of c/2 for both resulting cycles.

\(\text{# pairs that split a cycle of size } c = \begin{cases} \frac{c}{2} & \text{if } 2i = c \\ c & \text{if } 2i \neq c \end{cases}\)

Now let’s consider the case where we select two elements in different cycles and end up merging them. In this case, we need to know how many elements are in the cycles associated with the two elements i and j that we’ve selected. Let’s call the cycle lengths c_i and c_j. Since we also don’t care about the particular elements that compose a given cycle (i.e. we only care about the sizes of the disjoint cycles for the permutation), we also need to consider the possibility that there are multiple cycles of the same length (which would make them indistinguishable in our treatment). Let’s define the number of cycles with length c_i to be m_i and the number of cycles with length c_j to be m_j. With this in mind there are generally m_im_j ways of selecting cycles of the appropriate size and c_ic_j ways of selecting elements within those cycles. The only exception is when m_i=m_j in which case there are m_i choose 2 ways to select cycles of the appropriate length.

\(\text{# pairs that merge cycles of sizes } c_i \text{ and } c_j = \begin{cases} \binom{m}{2} c_i^2 & \text{if } c_i = c_j \\ m_i m_j c_i c_j & \text{if } c_i \neq c_j \end{cases}\)

So what do we do with all of this? Well, we know what the probabilities are of the cycle structure changing and we know we need to get to a state where there are c 1-cycles. Seems like a fine time for a Markov Chain! the only thing we’re still missing is the initial probabilities of the cycle structure for a random permutation but we actually derived this in part 2. Let’s call some cycle structure of a permutation p (for “partition” since this can also be thought of as an integer partition of n)

\(P(p) = P(p|K) P(K)\)

In part 2 we determined that

\(P(p|K) = \frac{k!}{\displaystyle \prod_{p \in P_k} p! \cdot \prod_{s \in \text{\{# partitions of size s\}}} s!}\)

and in part 1 we determined that

\(P(K) = \binom{10}{k} \cdot \sum_{i=0}^{10} \frac{(-1)^i}{i!}\)

Now with the intial probabilities and transition probabilities, all we need to do is pull this into an absorbing Markov chain model to compute the expected number of steps.

And viola! If do all those computations, we get an answer of 40.407 swaps.

Whew, that was lot! I Hope that solution made sense (and was correct lol)! Feel free to comment with any thoughts of feedback you had on this problem or if you approached it differently. As always, thanks for reading!