Interpretación probabilística del lema de Burnside

Question

El Lema de Burnside afirma que $N$ el número de órbitas cuando un grupo $G$ actúa en un conjunto $X$ está dada por $$N = \frac {1}{|G|} \sum_ {g \in G} | \text {Fix } g|$$

La prueba estándar consiste en aplicar el teorema del estabilizador de órbita a los representantes $x_1, \cdots , x_N$ de cada órbita:

$$ \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$$

Una forma alternativa de decirlo es decir que el número de órbitas es igual al promedio de puntos fijos. ¿Hay alguna forma probabilística de interpretar esto?

He visto el hilo de MathOverflow http://mathoverflow.net/questions/50033/intuitive-explanation-of-burnsides-lemma .

Answer 1

Si un no-etiqueta $G$ actúa sobre sí mismo por conjugación, entonces el Lema de Burnside (que según Peter Neumann debería ser llamado el Cauchy-Frobenius Lemma ) puede utilizarse para calcular la probabilidad $P(G)$ que dos elementos de $G$ viaje de ida y vuelta: $P(G) \leq \frac {5}{8}$ . Y se puede decir mucho más, ver por ejemplo aquí .

Answer 2

Veamos primero el caso en el que hay una sola órbita. Considere algún punto $x$ en esa órbita y preguntar cuál es la probabilidad de que una persona elegida al azar $g \in G$ arreglos $x$ . Bueno, cualquier $g$ trazará un mapa $x$ a algunos punto en la órbita. Si usted cree que cada punto de la órbita es tan probable como cualquier otro que se obtenga como $gx$ (con nuestro elegido $x$ y al azar $g$ ), entonces la probabilidad de que $g$ mapas $x$ a cualquier punto específico $y$ en la órbita es $1/$ (tamaño de la órbita). En particular, la probabilidad de que $g$ arreglos $x$ es $1/$ (tamaño de la órbita). Aplica esto a cada punto $x$ en la órbita, y obtienes que el número esperado de puntos fijos, para una $g$ es 1. Es el lema de Burnside para el caso de una sola órbita.

En el caso de varias órbitas, sólo hay que tomar la suma sobre todas las órbitas.

Este argumento no es una prueba completa, debido a la parte de "Si crees". Rellenar los detalles de esa parte sería esencialmente equivalente a la prueba habitual. Espero, sin embargo, que esta parte sea intuitivamente plausible, y, si lo es, entonces esto da una explicación intuitiva probabilística del Lema de Burnside.