# Find an average number by using group action

In a party there are $$n$$ individuals. Each of them gives a present in the party. At the end of the party the presents are distributed randomly to each participant. How many individuals receive in average their own presents?

We want to solve the problem from the perspective of a particular group action $$f: G \times M \rightarrow M$$ and a fixed set, $$M^g = \{ x \in M\mid g\cdot x = x \}$$. I do not know how to go from here.

Do you have any suggestion or a solution proposal? Thanks.

• The probability you get your own present is $\frac1n$, so the expected number of "own presents" each person gets is $\frac1n$, so by linearity of expectation, the expected total number of "own presents" is $n\frac1n=1$.
– Karl
Commented Dec 17, 2022 at 1:48
• Thanks. But the aim is to use a group action argument. Commented Dec 17, 2022 at 2:21

All this boils down to is a shuffling of the presents, and the question how many fixed points.

We have $$S_n$$ acting on $$n$$ points.

By Burnside's lemma, $$\lvert M/G\rvert =1/\lvert G\rvert \sum \vert M^g\rvert.$$ The number of orbits is the average number of fixed points.

We get $$\lvert M/G\rvert =1,$$ because, as we know, the action is transitive.

• It would be ideal if you left the punctuation marks where they belong. Instead of $$, it should be ,$$. Commented Dec 17, 2022 at 4:27
• Thanks for the tip. I think I was told this before, but didn't get it. @kabenyuk Commented Dec 17, 2022 at 5:03
• Thanks. What is the argument that the right hand side is $1$ ? Commented Dec 17, 2022 at 10:55
• You are saying, since the action is transitive, $|M/G| = 1.$ I do not understand how you get $1$. Can you explain this also in the context of the given problem ? Commented Dec 17, 2022 at 11:37
• Transitive actions only have $1$ orbit. For every two presents, there's a permutation that takes one to the other. $S_n$ is famous for that. Commented Dec 17, 2022 at 12:33

I will here take the detour of walking through matrix representations of groups. If you have not studied linear algebra and matrices, this answer may not be so useful.

The group which describes the text is a permutation group.

The group action can in this case be defined in terms of the trace on the trivial matrix representation of the group -- the set of permutation matrices $$\bf A$$ of size $$n\times n$$ (where the group operation corresponds to matrix multiplication).

$$Tr({\bf A}) = \sum_{i=1}^n {\bf A}_{ii}$$

Now remember that each matrix $$\bf A$$ represents one particular permutation. One particular table of present-givings if you will. As we are interested in the average over all permutations, we are not finished yet, but now we want to calculate the expected value over all such $$\bf A$$ in our representation.

Can we prove somehow, for example by symmetry that the average representation matrix will be the $$n\times n$$ matrix filled with $$1/n$$ values everywhere, then we will have confirmed the result in Karl's comment above due to the linearity of trace and the expectation operators allows them to change place.