Probabilistic Interpretation of Burnside's Lemma

Question

Burnside's Lemma states that $N$, the number of orbits when a group $G$ acts on a set $X$ is given by $$N = \frac{1}{|G|} \sum_{g \in G} |\text{Fix } g|$$

The standard proof involves applying the orbit-stabilizer theorem to representatives $x_1, \cdots, x_N$ from each orbit:

$$\sum_{g \in G} |\text{Fix } g| = \sum_{i = 1}^N \sum_{x \in \text{Orb }x_i} |\text{Stab }x|= \sum_{i = 1}^N |\text{Orb }x_i||\text{Stab }x_i| = N \cdot G$$

An alternate way of stating this is to say that the number of orbits is equal to the average number of fixed points. Is there some probabilistic way of interpreting this?

I have seen the MathOverflow thread https://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma.

Answer 1

If a non-abelian $G$ acts on itself by conjugation, then the Burnside Lemma (which according to Peter Neumann should be called the Cauchy-Frobenius Lemma) can be used to calculate the chance $P(G)$ that two elements of $G$ commute: $P(G) \leq \frac{5}{8}$. And much more can be said, see for example here.

Answer 2

If you randomly uniformly choose elements $g\in G$ and $x\in X$, the probability that $g$ fixes $x$ is $\frac N{|X|}$:

$$ \textsf{Pr}(gx=x)=\frac1{|X|}\frac1{|G|}\sum_{g\in G}\sum_{x\in X}1_{gx=x}=\frac1{|X|}\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}g\,|=\frac N{|X|}\;. $$

Not sure whether that's the sort of interpretation you had in mind...

Answer 3

Let's look first at the case where there's just a single orbit. Consider some point $x$ in that orbit and ask what's the probability that a randomly chosen $g\in G$ fixes $x$. Well, any $g$ will map $x$ to some point in the orbit. If you believe that each point in the orbit is as likely as any other to be obtained as $gx$ (with our chosen $x$ and random $g$), then the probability that $g$ maps $x$ to any specific point $y$ in the orbit is $1/$(size of orbit). In particular, the probability that $g$ fixes $x$ is $1/$(size of orbit). Apply this to each point $x$ in the orbit, and you get that the expected number of fixed points, for a random $g$, is 1. That's Burnside's Lemma for the case of a single orbit.

For the case of several orbits, just take the sum over all the orbits.

This argument isn't a complete proof, because of the "If you believe" part. Filling in the details of that part would be essentially equivalent to the usual proof. I hope, though, that this part is intuitively plausible, and, if it is, then this gives a probabilistic intuitive explanation of Burnside's Lemma.