An analysis of the last round matching problem (Q855455)

This paper investigates the ``Hats Problem'' (Pierre de Montmort, 1713), considered as a single-round version of the matching problem, and its extension to multi-round matching. These problems are stated as follows: (P1) Single-round matching problem: suppose that each of \(n\) men at a party throws his hat into the center of the room. The hats are first mixed up, and then each man randomly selects a hat. What is the probability that exactly \(k\) of the men select their own hats? What is the expected number of the people that select their own hats? The number of matches with \(n\) men is the distribution of a random variable \(X_n\). The so-called Montmort random variable \(X_n\) is known to have an approximate Poisson distribution. The problem (P1) is extended to the following multi-round matching: (P2) Suppose that those men choosing their own hats depart, while the others put their selected hats in the center of the room, mixing them up, and then selecting them again. Suppose also that this process continues until each individual gets its own hat. What is the expected number of rounds that is necessary, and what is the expected number of men, \(L_n\), at the last round (starting with \(n\) individuals)? The purpose of this paper is to investigate solutions to the problems (P1) and (P2). Section 2 provides the mathematical formulation of the problem together with some remarkable properties of the Montmort random variable \(X_n\). Recursive relations for the expectation \(E(L_n)\), and estimation of the distribution \(q_{n, m} = P(L_n = m)\) are given. Section 3 proves the main results, using the convolution method. Section 4 shows an estimate of order \(n^{-1/2}\) on the speed of \(E(L_n)\) convergence, and presents a table for the distribution of \(L_n\), \(2 \leq n\leq 15\), along with numerical approximations of the limiting values. Related problems (e.g. the Christmas gift problem), questions, and helpful remarks are also enclosed.