I have a party and I invite $n$ people. I create a seating plan and assign each person a specific seat. When they arrive, however, they completely ignore the plan and sit down randomly. I’m strict though, and insist that my guests sit in the arranged order. How many pairs of guests should we expect to only have to swap places with each other in order for the plan to be fulfilled?
I’ve attempted to solve this but so far seem to have failed.
Here’s my attempt so far:
We can consider the number of permutations of the set of guests such that $i$ pairs of guests only have to swap to reach their positions in the ‘assigned’ configuration. We can then divide this quantity by the total number of possible permutations to obtain the probability that we are in a configuration such that exactly $i$ pairs of guests only need to swap to reach their assigned seats.
For $n$ guests, let $M$ be the number of pairs who can do such a swap. We have the following general expression as a weighted sum of probabilities for each of the possible numbers of pairs in the set.
$$\mathbb{E}[M] = \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} i \cdot Pr(M = i)$$
$$ = \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} i \cdot \frac{1}{n!} \cdot {n \choose 2} {n – 2 \choose 2} {n – 4 \choose 2} \dots {n – 2(i – 1) \choose 2} (n – 2i)!$$
We can calculate the number of permutations mentioned earlier by considering how each one may be constructed. Consider the case of $5$ guests. For a permutation where a single pair can swap, we can choose $2$ guests, for which there are $5 \choose 2$ choices and then let the rest of the guests vary, for which there are $3!$ possibilities. We multiply these quantities to obtain the total number of possibilities. For two pairs, we choose $2$ guests out of the $5$, then choose $2$ more out of the remaining $3$. We then have only one possible guest for the last seat. The general case is a simple extension of this. We have $5!$ total possible permutations of the 5-guest set, so we divide by $5!$.
So in the case of $5$ guests we have
$$\mathbb{E}[M] = 1 \cdot \frac{{5 \choose 2} 3!}{5!} + 2 \cdot \frac{{5 \choose 2} {3 \choose 2}}{5!} = 1$$
In this case, then, we expect exactly one pair of guests to only have to swap their places in order to reach their assigned seats. Quite a pleasing result.
However, when I extend this to $6$ and $7$ guests, I get a different result. I think $\mathbb{E}[M]$ should be a constant and not depend on $n$.
I then realised that we could perhaps make use of the linearity of expectation here, and write down something like
$$\mathbb{E}[M] = \frac{1}{5!} {5 \choose 2} 3! + \frac{1}{5!} {5 \choose 2} 3! = 1$$
for two pairs in a set of five guests, which gives the same result.
Once again though, the value changes with $n$ if we add more pairs, and rather dramatically.
So, what am I doing wrong here? Am I missing a really easy trick, and what exactly is wrong with my solution?
Best Answer
I am not sure I follow your logic $100$%, but here is how I would solve the problem.
You are counting, in a random permutation of $\{1, 2, \dots, n\}$, the number of pairs of positions that have simply swapped places. Call this number $M$. Luckily you only want the expected value $E[M]$ so linearity of expectation comes to the rescue.
For $1 \le i < j \le n$, let $X_{ij}$ be the indicator random variable for whether $i$ and $j$ have swapped places. E.g. if the permutation is $(3,5,1,2,4)$ then $X_{13} = 1$ and all other $X_{ij} = 0$. Then $M = \sum_{1 \le i < j \le n} X_{ij}$.
Meanwhile $\forall i, j: E[X_{ij}] = P(X_{ij} = 1) = {(n-2)! \over n!} = {1 \over n(n-1)}$ because the other $(n-2)$ positions are unconstrained.
So by linearity of expectation (and despite the various $X_{ij}$'s being clearly dependent), we have:
$$E[M] = \sum_{1 \le i < j \le n} E[X_{ij}] = {n \choose 2} \cdot {1 \over n(n-1)} = {1 \over 2}$$
So this is a constant (independent of $n$) as you suspected, but not the value you calculated.
Sanity check: for $n=3$, out of the $6$ permutations, $3$ of them have $M=1$ (choose any of $3$ pairs), and the other $3$ (identity and two rotations) have $M=0$, for an average of $E[M] = 1/2.$
As I said, I am not sure I follow your logic $100$%, but let me try to debug at least one piece of it. In your formula:
$$E[M] = 1 \cdot \frac{{5 \choose 2} 3!}{5!} + 2 \cdot \frac{{5 \choose 2} {3 \choose 2}}{5!} = 1$$
You counted the number of permutations with $1$ pair swapped to be ${5 \choose 2}3!$ but this is incorrect. If the ${5 \choose 2}$ denotes the pair which have swapped, then you need to make sure there is not another swapped pair among the remaining $3$. So you cannot multiply by $3!$ since that allows any permutation among the other $3$. Indeed, among the $3!=6$ permutations, exactly $3$ of them have no swapped pair (identity and the two rotations). So that numerator should have been ${5 \choose 2}\color{red}{3}$ instead.
You counted the number of permutations with $2$ swapped pairs to be ${5\choose 2}{3 \choose 2}$ but this is exactly double counting, since either of the two pairs could have been chosen first. So that numerator should have been ${5 \choose 2}{3 \choose 2}\color{red}{/2}$ instead.
So the correct formula would be:
$$E[M] = 1 \cdot \frac{{5 \choose 2} \color{red}{3}}{5!} + 2 \cdot \frac{{5 \choose 2} {3 \choose 2}\color{red}{/2}}{5!} = {10 \cdot 3 + 2 \cdot 10 \cdot 3 /2 \over 5!} = {60 \over 120} = {1 \over 2}$$
In general, your method finds $P(M=i)$ but I think that is actually a (much?) harder problem than finding $E[M]$ using my method.