Cycles of a shuffle
Five people each write their name on a card. The cards are shuffled uniformly at random and dealt back, one per person. Each person then hands their card to the person whose name is on it, which splits the five people into cycles (someone who receives their own card forms a cycle of length ).
Find the expected number of cycles.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Write the number of cycles as a sum of indicators, one for each element. Which element of a cycle could “represent” it? Or count weights: give each person the weight .
The length of the cycle containing a given person is uniform on . Try to see why by following the cycle from that person.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Each cycle of length contains people, so giving every person the weight (where is the length of their own cycle) counts each cycle exactly once. It remains to find the law of the length of one person's cycle.
Step 1: counting by weights. If is the length of the cycle containing person , then because the members of a cycle of length contribute . By symmetry all have the same law, so .
Step 2: the law of . Follow the cycle from person : they point to someone, who points to someone else, and so on. The first step closes the cycle with probability (person drew their own card). If not, the next person points back to with probability , since their card is uniform among the cards left. Continuing, for (the product telescopes). So is uniform on .
Step 3: combine.
In general. A random permutation of elements has cycles on average.