Wahrscheinlichkeitsmaße in unendlichen Gruppen

Karsten Hiddemann

29. April 2003

Zusammenfassung In dem relativ neuen, als “statistische Gruppentheorie” bezeichneten Teil der Gruppentheorie, sind typische Ergebnisse Aussagen wie “ein zufälliges Element (oder Tupel von Elementen) einer Gruppe G hat Eigenschaft P mit Wahrscheinlichkeit p”. Da solche Aussagen stark abhängig davon sind, wie man Wahrscheinlichkeit auf Gruppen definiert bzw. wie man Mengen in Gruppen mißt, sollen hier neue Zugänge zur Definition von Maßen gegeben werden.

1 Ziel

Es werden Ansätze untersucht, zu einer gegebenen unendlichen Gruppe G Maße zu konstruieren, die den folgenden Vorgaben gerecht werden:

(C1) Das Maß μ sollte natürlich sein, d.h. es sollte unseren Erwartungen entsprechen, was die Größe verschiedener Mengen betrifft.

(C2) μ sollte sensibel sein, d.h. intuitiv verschieden große Mengen sollten auch ein unterschiedliches Maß besitzen.

(C3) μ(S), oder eine ziemlich genaue Schranke, sollte für “natürliche” Mengen einfach berechenbar sein.

(C4) μ sollte einen natürlichen Erzeuger zufälliger Elemente erlauben.

2 Atomare Wahrscheinlichkeitsmaße

Erinnerung 2.1. Ein Maß μ auf einer Menge X heißt atomar, falls X abzählbar und S μ-meßbar für alle S ⊆ X. Aufgrund der Additivität wird μ in diesem Fall eindeutig durch die Einermengen {ω}, ω ∈ X, bestimmt:

μ(S) = ∑_{ω∈S} μ({ω})

Wir schreiben daher im folgenden statt μ({ω}) auch μ(ω) für ω ∈ X.

Wir betrachten speziell atomare Wahrscheinlichkeitsmaße auf der freien Gruppe G = F_{n}. Dazu fixieren wir eine beliebige Basis {x_{1}, …, x_{n}} von G, denn es gilt das folgende

Lemma 2.2. Das singuläre Maß ist das einzige Aut F_{n} invariante Wahrscheinlichkeitsmaß.

Beweis. Für g^{h} := hgh^{−1} gelte also μ(g^{h}) = μ(g) ∀h ∈ G. Da G unendlich ist, folgt wegen der Additivität und Beschränktheit von μ für g ≠ 1 damit μ(g) = 0, denn sonst wäre μ({g^{h} | h ∈ I}) = ∑_{h∈I} μ(g) = |I| · μ(g) > 1 für ein genügend groß gewähltes I ⊆ G. Für g = 1 gilt 1^{h} = 1 und mit dem vorigen folgt μ(1) = 1.

Definition 2.3. Eine Funktion c : G → N heißt Komplexität oder auch Komplexitätsfunktion, falls für alle n ∈ N gilt, daß das Urbild c^{−1}(n) ⊆ G endlich ist.

Beispiel 2.4. Sei G eine endlich erzeugte Gruppe und S ⊆ G eine erzeugende Menge von G. Die Längenfunktion

l_{S}(g) = min{n | g = y_{1} … y_{n}, y_{i} ∈ S ∪ S^{−1}}

ist eine Komplexität auf G.

Bemerkungen 2.5.

• Besitzt G eine Komplexität, so ist G also insbesondere abzählbar. Durch geeignete Verallgemeinerungen, z.B. mit reellwertigen Komplexitäten, kann man diesen Begriff aber geeignet verallgemeinern.

• Ist l_{S} wie oben und H < G, so ist l_{S}|_{H} ebenfalls eine Komplexität auf H, dies muß aber nicht notwendigerweise mehr eine Längenfunktion auf H sein.

Definition 2.6. Sei c : G ↦ N eine Komplexität und μ ein Maß auf G. Wir nennen μ c-invariant, falls μ(u) = μ(v) für alle u, v ∈ G mit c(u) = c(v).

Wir interessieren uns insbesondere für komplexitätsinvariante Maße. Bezeichne C_{k} die Sphäre C_{k} = {ω ∈ G | c(ω) = k} und B_{n} den Ball B_{n} = {ω ∈ G | c(ω) ≤ n}, so ist der Ansatz zur allgemeinen Konstruktion von Maßen, die unseren Wünschen entsprechen, das folgende

Lemma 2.7. Sei μ ein atomares Maß und c eine Komplexität auf G.

a) Ist μ c-invariant, so ist d_{μ} : N → R, d_{μ} : k ↦ μ(C_{k}) ein Wahrscheinlichkeitsmaß auf N.

b) Ist d : N → R ein Wahrscheinlichkeitsmaß auf N, so ist p_{c,d} : G → R,

p_{c,d} : ω ↦ \frac{d(c(ω))}{|C_{n}|}, n = c(ω)

eine Funktion, die ein atomares c-invariantes Maß auf G liefert.

Man sucht jetzt also geeignetes c und d, die den Vorgaben (C1) - (C4) genügen.

3 Von Random Walks erzeugte Maße

Wir untersuchen zunächst die Erzeugung zufälliger Elemente. Im Allgemeinen werden zufällige Elemente erzeugt, indem man ein Wort der Länge l generiert und Relationen anwendet, dies entspricht einem Random Walk im Cayleygraphen der Gruppe. Sei M_{n} der Monoid zu F_{n} mit den Erzeugenden x_{1}, X_{1}, …, x_{n}, X_{n} und dem Homomorphismus π : M_{n} → F_{n}, welcher x_{i} auf x_{i} und X_{i} auf x_{i}^{−1} abbildet. Dann kann man einen Random Walk der Länge k im Cayleygraphen durch ein Wort von M_{n} beschreiben.

Feststellung 3.1. Sei d : N → R eine Wahrscheinlichkeitsverteilung, c eine Komplexität auf M_{n}, μ̃ = μ_{c,d} ein c-invariantes atomares Maß auf M_{n}. Die Wahrscheinlichkeit, daß ein Random Walk das Element x erzeugt, ist

μ(x) = ∑_{π(ω)=x} μ̃(ω)

Lemma 3.2. Für den Erwartungswert der geodätischen Länge von x in Γ(F_{n}), welches von einem Random Walk der Länge k erzeugt wird, gilt die Abschätzung

\frac{n − 1}{n}k ≤ E(l_{geod}(x)) ≤ k

Beweis. Verfolgt man die schrittweise Änderung der geodätischen Länge beim Random Walk, so entspricht dies einer Bewegung auf ℕ ∪ {0} mit Spiegelung in Null. In Null beträgt die Wahrscheinlichkeit für eine Bewegung nach rechts 1, ansonsten hat man Wahrscheinlichkeiten p = \frac{2n−1}{2n} für rechts und q = \frac{1}{2n} für links (in diesem Fall läuft man die zuvor gewählte Kante im Graphen wieder zurück). Statt an Null zu spiegeln betrachten wir nun den Lauf auf ℤ ohne Spiegelung an Null, der ursprüngliche Erwartungswert von l ist mindestens so groß wie der Erwartungswert in diesem Fall. Bei k Schritten vollzieht man m Rechtsschritte mit der Wahrscheinlichkeit \binom{k}{m} · p^{m} · q^{k−m}, mit dem Endpunkt l′ = m − (k − m) = 2m − k. Daher ist die Zufallsvariable l′ eine lineare Transformation der Zufallsvariablen m, verteilt anhand der Binomialverteilung. Da gilt

E(m) = ∑_{m=0}^{k} m\binom{k}{m}p^{m}q^{k−m} = pk ∑_{m=1}^{k} \binom{k − 1}{m − 1}p^{m−1}q^{k−1−(m−1)}

= pk ∑_{m=0}^{k−1} \binom{k − 1}{m}p^{m}q^{k−1−m} = pk(p + q)^{k−1} = pk

erhält man für den Erwartungswert E(l_{geod}(x)) die untere Schranke

E(l′) = 2E(m) − k = 2pk − k = \frac{n − 1}{n}k

Die obere Schranke ist klar.

4 Induzierte Maße auf endlichen Faktorgruppen

Wir würden für Mengen gerne natürliche Maße haben, z.B. das Maß \frac{1}{2} für Wörter gerader Länge oder das Maß \frac{1}{m} für Untergruppen H < F mit Index |F : H| = m. Ein Problem stellt hierbei der sogenannte Einfluß kurzer Elemente dar: Sei μ ein Wahrscheinlichkeitsmaß und C_{k} wie oben, dann folgt aus ∑_{k} μ(C_{k}) = 1, daß μ(C_{k}) → 0 für k → ∞. Da 1 ∈ H gilt für m ≫ \frac{1}{μ(1)} dann aber μ(H) ≥ μ(1) ≫ \frac{1}{m}. Bei dem Arbeiten mit Wahrscheinlichkeiten auf endlichen Gruppen werden Maße bevorzugt, welche gut verträglich sind mit “großen” endlichen Faktoren F_{n}/R, welche z.B. eine sinnvolle Schranke liefern bei dem Gesamtvarianzabstand

\frac{1}{2} ∑_{\overline{g}∈F_{n}/R} |μ(\overline{g}) − \frac{1}{|F_{n} : R|}|  (1)

für das induzierte Maß auf F_{n}/R. Aus praktisch dem gleichen Grund kann diese natürliche Bedingung nicht erfüllt werden, denn \frac{1}{2}|μ(1) − \frac{1}{m}| mit m = |F_{n} : R| ist eine untere Schranke welche nicht gegen 0 konvergiert für m → ∞. Diese unentschuldbare Abhängigkeit von dem Maß kurzer Elemente ist eine von vielen Gründen für die folgende (womöglich kontroverse) metamathematische These:

Es gibt kein atomares Maß auf unendlichen Gruppen, welches unseren Erwartungen zur Größe bestimmter Mengen in der Gruppe gerecht wird.

Man kann versuchen unnatürlich große Wahrscheinlichkeiten kurzer Elemente auszuschliessen, indem man für ein Element gR in der Faktorgruppe F_{n}/R mit B_{l} wie oben das normalisierte Maß “großer” Elemente in gR verwendet:

\overline{μ}_{l}(gR) = \frac{μ((F_{n} \ B_{l}) ∩ gR)}{μ(F_{n} \ B_{l})}

Ein Maß μ = \overline{μ}_{l} ist “gut”, wenn der Gesamtvarianzabstand (1) für l ≪ m nach oben beschränkt ist durch \frac{1}{e} oder eine andere sinnvolle Konstante, oder wenn dieser exponentiell abnimmt für wachsendes l, d.h. o(e^{−cl}) ist. Wir nähern uns also dem klassischen Konzept eines Random Walk auf einer Gruppe: Bilder von “ausreichend langen” Elementen zu nehmen bedeutet einen ausreichend langen Random Walk bezüglich der charakteristischen Wortlänge l auf der Faktorgruppe F_{n}/R mit den Erzeugern x_{1}R, …, x_{n}R durchzuführen.

Definition 4.1. Die Mischzeit ist definiert als das minimale l_{0}, so daß

∥P_{l_{0}} − U∥ = \frac{1}{2} ∑_{\overline{g}∈F_{n}/R} |P_{l_{0}}(\overline{g}) − \frac{1}{|F_{n} : R|}| < \frac{1}{e}

wobei P_{l}(\overline{g}) die Wahrscheinlichkeit ist, daß ein Random Walk von Länge l bei dem Element \overline{g} stoppt und U die Gleichverteilung auf F_{n}/R ist.

Erinnerung 4.2. Ab der Mischzeit konvergiert das von Random Walks erzeugte Maß exponentiell schnell gegen die Gleichverteilung:

∥P_{kl_{0}} − U∥ = \frac{1}{2} ∑_{\overline{g}∈F_{n}/R} |P_{kl_{0}}(\overline{g}) − \frac{1}{|F_{n} : R|}| = o(e^{−ck})

Wir können nun ein alternatives Kriterium für gutes Verhalten von Maßen auf endlichen Faktorgruppen aufnehmen in unseren ursprünglichen Wunschzettel:

(C1*) Für jede endliche Faktorgruppe G = F_{n}/R existiert ein l_{0}, so daß

\frac{1}{2} ∑_{\overline{g}∈F_{n}/R} |\overline{μ}_{kl_{0}}(\overline{g}) − \frac{1}{|F_{n} : R|}| = o(e^{−ck})

Es ist recht einfach zu sehen, daß das Kriterium (C1*) von einer großen Klasse von Maßen erfüllt wird:

Satz 4.3. Erfüllt die Wahrscheinlichkeitsverteilung d(k) die Bedingung d(k) > 0 für unendlich viele k, dann erfüllt das induzierte Maß \overline{μ}_{l} auf der endlichen Faktorgruppe G = F_{n}/R die Bedingung (C1*).

Beweis. Sei m = |G|. Identifiziere die Wahrscheinlichkeitsverteilungen auf G mit (p_{1}, …, p_{m}) ∈ ℝ^{m}, d.h. p_{1} + … + p_{m} = 1, p_{i} ≥ 0 ∀i. Dann entspricht die Menge der Wahrscheinlichkeitsverteilungen der konvexen Hülle Δ von den Verteilungen E_{g} mit E_{g}(h) = 1, falls g = h und 0 sonst. Der Gesamtvarianzabstand

∥P − Q∥ = \frac{1}{2} ∑_{g∈G} |P (g) − Q(g)|

ist dann eine Metrik auf Δ. Ein Schritt eines Random Walks in dem Cayley-Graphen induziert eine affine Transformation τ : ℝ^{m} → ℝ^{m} auf den Verteilungen durch

τ : E_{g} ↦ \frac{1}{2n} ∑_{h adjazent zu g} E_{h},

d.h. τ hat den Fixpunkt U = (1/m, …, 1/m) ∈ Δ.

Verschieben wir nun den Ursprung des Koordinatensystems von ℝ^{m} nach U, so wird der Abstand ∥X − U∥ zu einer Norm, welche wir nun kurz mit ∥X∥ bezeichnen und τ wird dann auf dem durch Δ gegebenen Unterraum zu einem linearen Operator. τ ist eine Selbstabbildung von Δ auf sich, genauso für τ^{k}(Δ), daher haben wir

∥τ^{k+1}(E_{g})∥ ≤ ∥τ^{k}(E_{g})∥

Nachrechnen ergibt für die euklidische Norm ∥τ(E_{g})∥_{E} < ∥E_{g}∥_{E}, d.h. es gilt

∥τ∥_{E} = max_{X∈Δ,X≠0} \frac{∥τ(X)∥_{E}}{∥X∥_{E}} < 1

für die natürliche zugehörige Matrixnorm. Es folgt ∥τ^{k}(X)∥ → 0 für k → ∞, die Konvergenz ist sogar exponentiell schnell: ∥τ^{k}(X)∥_{E} = o(c^{k}). Da im endlichdimensionalen Fall jeweils zwei Normen zueinander äquivalent sind, gibt es ein C, so daß

\frac{1}{C} ∥X∥_{E} < ∥X∥ < C∥X∥_{E}

und damit folgt, daß ∥τ^{k}(X)∥ = o(c^{k}). Wir haben in unserer neuen Notation

\frac{1}{2} ∑_{g∈G} |\overline{μ}_{l}(g) − \frac{1}{m}| = ∥\overline{μ}_{l}∥ = ∥\frac{1}{∑_{k≥l} d(k)} ∑_{k≥l} d(k)τ^{k}(E_{1})∥

= \frac{1}{∑_{k≥l} d(k)} ∥∑_{k≥l} d(k)τ^{k}(E_{1})∥ ≤ \overline{∑_{k≥l} d(k)} ∥∑_{k≥l} d(k)τ^{l}(E_{1})∥

= ∥τ^{l}(E_{1})∥ · \frac{∑_{k≥l} d(k)}{∑_{k≥l} d(k)} = ∥τ^{l}(E_{1})∥.

Wir sehen, daß die Wahrscheinlichkeitsverteilung auf G, erzeugt durch einen Random Walk von Länge l oder größer, genauso schnell gegen die Gleichverteilung konvergiert wie die Wahrscheinlichkeitsverteilung nach l Schritten beim ursprünglichen Random Walk, dies zeigt, daß \overline{μ}_{l} auf G die Bedingung (C1*) erfüllt.

5 Wachstumsfunktion und asymptotische Dichte

Zuletzt wollen wir noch das asymptotische Verhalten von Mengen untersuchen.

Definition 5.1. Ein Pseudomaß auf G ist eine nichtnegative reellwertige Funktion, die auf bestimmten Teilmengen von G definiert ist. Ein Pseudomaß μ heißt atomar, wenn μ(S) definiert ist für jedes endliche S ⊆ G.

Definition 5.2. Wir definieren die sphärisch-asymptotische Dichte ρ^{(s)} durch

ρ_{k}^{(s)}(R) = \frac{μ(R ∩ C_{k})}{μ(C_{k})}, ρ^{(s)}(R) = lim_{k→∞} ρ_{k}^{(s)}(R)

und die kugel-asymptotische Dichte ρ^{(d)} durch

ρ_{k}^{(d)}(R) = \frac{μ(R ∩ B_{k})}{μ(B_{k})}, ρ^{(d)}(R) = lim_{k→∞} ρ_{k}^{(d)}(R)

für R ⊆ G. Man kann in der obigen Definition auch lim sup verwenden statt lim.

Lemma 5.3. Ist μ ein atomares Pseudomaß auf G, so auch ρ^{(s)} und ρ^{(d)}.

Lemma 5.4. Sei μ Pseudomaß auf G mit lim_{k→∞} μ(B_{k}) = ∞. Dann existiert ρ^{(s)}(R), wenn ρ^{(d)}(R) existiert und in diesem Fall gilt Gleichheit: ρ^{(s)}(R) = ρ^{(d)}(R).

Beweis. Sei x_{k} = μ(R ∩ B_{k}) und y_{k} = μ(B_{k}). Es gilt y_{k} < y_{k+1} und lim y_{k} = ∞. Nach Stolz Theorem [3] ist dann

lim_{k→∞} \frac{x_{k}}{y_{k}} = lim_{k→∞} \frac{x_{k} − x_{k−1}}{y_{k} − y_{k−1}}

und wegen der Additivität gilt nach Definition von B_{k} und C_{k}

ρ^{(d)}(R) = lim_{k→∞} \frac{μ((R ∩ B_{k}) \ B_{k−1})}{μ(B_{k} \ B_{k−1})} = lim_{k→∞} \frac{μ(R ∩ C_{k})}{μ(C_{k})} = ρ^{(s)}(R)

Unter diesem Gesichtspunkt sprechen wir nun allgemein von den Dichten ρ. Asymptotische Dichten sind ein nützliches Werkzeug zum Beschreiben des Verhaltens von Mengen im Unendlichen, allerdings gibt es viele natürliche Mengen, welche hiermit leider nicht meßbar sind. Man sieht z.B. sofort, daß ρ(E_{n}) für

E_{n} = {ω ∈ F_{n} | |ω| gerade }

nicht definiert ist. Die folgenden Theoreme zeigen, daß ρ nicht sensibel genug ist:

Satz 5.5 (Woess [4]). Ist N eine normale Untergruppe von F_{n}, n ≥ 2, mit unendlichem Index, so ist ρ(N) = 0.

Erinnerung 5.6. Wir nennen ein Element u ∈ F_{n} primitiv, falls es Teil einer freien Basis von F_{n} ist, bzw. wenn äquivalent gilt α(u) = x_{1} für ein α ∈ Aut F_{n}.

Satz 5.7. Sei F_{n} die freie Gruppe von endlichem Rang n ≥ 2. Dann gilt

ρ(Pr_{n}) = 0

wobei Pr_{n} die Menge der primitiven Elemente von F_{n} ist. Genauer, sei P (n, k) die Zahl der primitiven Elemente von Länge k in F_{n}, n ≥ 3, dann gibt es Konstanten c_{1} und c_{2} mit

c_{1} · (2n − 3)^{k} ≤ P (n, k) ≤ c_{2} · (2n − 2)^{k}

Proposition 5.8. In F_{2} ist die Zahl der primitiven Elemente P (2, k)

(a) größer als \frac{4}{\sqrt{3}} · (\sqrt{3})^{k} falls k ungerade ist.

(b) größer als \frac{4}{3} · (\sqrt{3})^{k} falls k gerade ist.

Dies heißt, daß die “meisten” primitiven Elemente in F_{2} Konjugate primitiver Elemente kleinerer Länge sind. Dies ist nicht der Fall in F_{n} mit n > 2, wo die “meisten” primitiven Elemente von der Form u·x_{i}^{±1} ·v sind, wobei u und v beliebige Elemente sind, die nicht von x_{i} abhängen.

Literatur

[1] A. Borovik, A. G. Myasnikov, V. Shpilrain, Measuring sets in infinite groups, Contemp. Math., Amer. Math. Soc. 298 (2002), 21–42.

[2] I. Kapovich, A. G. Myasnikov, P. Schupp, and V.Shpilrain, Generic-case complexity, decision problems in group theory and random walks, J. Algebra 264 (2003), 665–694.

[3] Guntram Hainke, Generische Komplexität gruppentheoretischer Entscheidungsprobleme I: Das Wortproblem, talk on [2] at the University of Dortmund, 2003

[4] W. Woess, Cogrowth of groups and simple random walks, Arch. Math. 41 (1983), 363–370.