Question

In the match problem, say that \((i, j), i

Short answer

(a) The expected number of pairs is \(E(pairs)=\binom{n}{2}\times\frac{1}{(n-1)(n-2)}\). (b) The recursive formula for the probability of having no pairs is \(Q_n = \frac{1}{n}\sum_{j=1}^{n-1} Q_{n-j}\). (c) The probability of having no pairs with 8 people, \(Q_8\), is \(\frac{1}{40320}\).

Step-by-step solution

(a) Expected Number of Pairs

To find the expected number of pairs, we should determine the total number of pairings and then the probability of any single pair being matched correctly. After that, we can calculate the expected number of pairs. First, let's determine the total number of pairings possible. This can be calculated as the number of permutations of the set of n people/indices, which is given by \(n!\). Next, let's determine the probability of a single pair (i, j) being matched correctly. For a pair (i, j) to be matched correctly, i must choose j's hat, and j must choose i's hat. The probability of this happening is, therefore, \(\frac{1}{n-1}\times\frac{1}{n-2}\). Now, since there are \(\binom{n}{2}\) possible pairs, the expected number of pairs can be calculated as the product of the probability of a single pair being matched and the number of pairs, which is: \(E(pairs)=\binom{n}{2}\times\frac{1}{(n-1)(n-2)}\)

(b) Recursive Formula for Probability of Having No Pairs

To derive a recursive formula for the probability of having no pairs, we can follow this process: Consider a cyclic permutation of the members. 1. If the cycle has length n, then no pairs are formed, and this occurs with the probability of \(Q_n\). 2. If the cycle has length smaller than n, say j, we remove this cycle from the permutation. Now we have \(n-j\) remaining elements, and their configuration has a probability of \(Q_{n-j}\). This means that the probability of having no pairs in a permutation of n elements can be expressed as the sum of the probabilities of all the configurations involving cycles with length smaller than n. So, we have: \(Q_n = \frac{1}{n}\sum_{j=1}^{n-1} Q_{n-j}\)

(c) Calculate Q8

To find \(Q_8\), we will use the recursive formula derived in part (b) and calculate the value of \(Q_n\) for each n smaller than 8: \(Q_1 = 1\) (Trivial Case) \(Q_2 = \frac{1}{2}(Q_1) = \frac{1}{2}\) \(Q_3 = \frac{1}{3}(Q_2) = \frac{1}{3}\times\frac{1}{2} = \frac{1}{6}\) \(Q_4 = \frac{1}{4}(Q_3) = \frac{1}{4}\times\frac{1}{6} = \frac{1}{24}\) \(Q_5 = \frac{1}{5}(Q_4) = \frac{1}{5}\times\frac{1}{24} = \frac{1}{120}\) \(Q_6 = \frac{1}{6}(Q_5) = \frac{1}{6}\times\frac{1}{120} = \frac{1}{720}\) \(Q_7 = \frac{1}{7}(Q_6) = \frac{1}{7}\times\frac{1}{720} = \frac{1}{5040}\) Now, using the same recursive formula, we can find \(Q_8\): \(Q_8 = \frac{1}{8}(Q_7) = \frac{1}{8}\times\frac{1}{5040}\) \(Q_8 = \frac{1}{40320}\) So, the probability of having no pairs when there are 8 people is \(\frac{1}{40320}\).