7
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ So if you choose a group element at random with uniform distribution, then the expected number of fixed points is equal to the number of orbits. I suppose you could use this for a probabilistic algorithm to guess the number of orbits, but computing the number of orbits deterministically is fast anyway. $\endgroup$
    – Derek Holt
    Jun 4, 2013 at 10:12

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting probabilistic application of Burnside's Lemma! I wonder if there's a probabilistic way of deriving/interpreting it. $\endgroup$ Jun 6, 2013 at 4:03
2
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.