Irrfahrten in Gruppen.

Vor zwei Wochen erwähnten wir Irrfahrten – zufällige Bewegungen, bei denen man jederzeit seine Richtung zufällig wählt (d.h. alle Richtungen sind gleichwahrscheinlich). Polya hatte 1912 bewiesen, dass man bei einer Irrfahrt in der Ebene mit an Sicherheit grenzender Wahrscheinlichkeit (d.h. Wahrscheinlichkeit 1) wieder zum Ausgangspunkt zurückkehrt, während das im drei-dimensionalen Raum oder z.B. in der hyperbolischen Ebene nicht der Fall ist. (“If you loose yor key in hyperbolic space you never find it back.”1)

Was ist der geometrische Hintergrund für die unterschiedlichen Rückkehrwahrscheinlichkeiten?

i-6780a29abb4574877367e20eb583923f-amsler_gitter.jpg

Eine etwas einfachere Aufgabe ist es, wenn man sich nicht in der gesamten Ebene, sondern nur auf einem Gitter (z.B. zwischen den Kreuzungen eines Strassennetzes) bewegt. Dann kann man die Rückkehrwahrscheinlichkeit mit elementarer Wahrscheinlichkeitstheorie berechnen und bekommt z.B. im oben abgebildeten Gitter die Rückkehrwahrscheinlichkeit 1.

Jeder Punkt der Ebene ist “nicht sehr weit entfernt” von einem Punkt des Gitters (genauer: hat Abstand höchstens 0.707… vom nächstgelegenen Gitterpunkt), es ist also plausibel, daß die Rückkehrwahrscheinlichkeit in der Ebene eng mit der Rückkehrwahrscheinlichkeit des Gitters zu tun haben sollte – und dies ist auch tatsächlich der Fall.

Das legt folgenden allgemeinen Ansatz nahe: wenn man die Rückkehrwahrscheinlichkeit in einem Raum bestimmen will, sucht man sich ein Gitter (mit der Eigenschaft, daß jeder Punkt des Raumes Abstand höchstens C von einem Gitterpunkt hat, für eine passende Konstante C) und berechnet die Rückkehrwahrscheinlichkeit auf diesem Gitter.

Gitter und Gruppentheorie

Die Ecken des oben abgebildeten Gitters entsprechen der Gruppe Z2={(m,n): m,n ganze Zahlen}.

Entsprechend kann man den 3-dimensionalen Raum “annähern” durch ein Gitter, dessen Ecken der Gruppe Z3={(m,n,l): m,n,l ganze Zahlen} entsprechen.

Auch in komplizierteren Räumen (z.B. der hyperbolischen Ebene) hätte man gern solche Gitter, in denen sich Rückkehrwahrscheinlichkeiten direkt berechnen lassen. Der Ansatz zur Konstruktion solcher Gitter ist über die Gruppentheorie.

Vor 3 Wochen hatten wir beschrieben, wie man jeder Gruppe einen Graphen zuordnet, ihren Cayley-Graphen. Die Bilder unten zeigen die Cayley-Graphen von Z und Z2:

i-56bedc2898046ffb35382474f153088f-Number-line.gif

Cayley-Graph von Z

i-6780a29abb4574877367e20eb583923f-amsler_gitter.jpg

Cayley-Graph von Z2

Der Cayley-Graph von Z kann offensichtlich so auf die 1-dimensionale Gerade R1 gelegt werden, dass jeder Punkt der Geraden Abstand höchstens 0.5 von einer der Ecken hat.
Die Ecken des Cayley-Graphen von Z2 haben von jedem Punkt der Ebene Abstand höchstens 0.707…

Allgemein gibt es in der Geometrie den Begriff der “kokompakten, freien Gruppenwirkung” auf einem Raum, der im Prinzip gerade besagt, dass der Cayleygraph der Gruppe isometrisch auf den Raum abgebildet werden kann, so dass jeder Punkt des Raumes beschränkten Abstand von einer Ecke des Cayley-Graphen hat. (Z wirkt also kokompakt auf der Gerade, Z2 wirkt kokompakt auf der Ebene.)

Noch ein instruktives Beispiel einer kokompakten, freien Gruppenwirkung auf der hyperbolischen Ebene:

i-574bc944262ac91dfe5e48e746f8f3ae-univeroc.gif

Quelle: http://mathworld.wolfram.com/UniversalCover.html

Die Gruppe ist in diesem Fall übrigens die Fundamentalgruppe der unten abgebildeten Brezelfläche. Das ist kein Zufall – zu jeder Fläche hat man eine kokompakte Wirkung der Fundamentalgruppe auf der universellen Überlagerung, vgl. TvF 65, und die universelle Überlagerung der Brezelfläche ist gerade die hyperbolische Ebene.

i-4b7e49d376cf27bd97af2f0016ae3455-UniversalCoverDoubleTorus_700.gif

Quelle: http://mathworld.wolfram.com/UniversalCover.html

Der Nutzen dieser Konstruktion ist, dass es einfacher ist, Rückkehrwahrscheinlichkeiten in solchen Cayley-Graphen zu berechnen.
Und – selbst wenn die Bewegung in der Gruppe eine andere ist als im ganzen Raum (man kann sich ja sozusagen nur zwischen den Ecken des Cayley-Graphen bewegen), kann bewiesen werden, dass man in einem Raum dann und nur dann mit Wahrscheinlichkeit 1 zum Ausgangspunkt zurückkehrt, wenn das selbe im Cayley-Graphen der (kokompakt und frei wirkenden) Gruppe der Fall ist.

Um zu wissen, ob man

auf der Gerade / in der Ebene/ im Raum / in der hyperbolischen Ebene

bei einer Irrfahrt (Brownschen Bewegung) mit Wahrscheinlichkeit 1 zum Ausgangspunkt zurückkommt, muss man also “nur” berechnen, ob dies

in den Cayley-Graphen von Z / Z2 / Z3 / der Fundamentalgruppe der Brezel

der Fall ist.

Volumenwachstum und Rückkehrwahrscheinlichkeit

In Kapitel 6 des unten2 verlinkten Buches von Varopoulos, Coulhon, Saloff-Coste wird bewiesen, dass man in einem Cayley-Graphen nur dann mit Wahrscheinlickeit 1 zum Ausgangspunkt zurückkehrt, wenn die Gruppe quadratisches Volumenwachstum hat.
(“Volumenwachstum” bezieht sich hier auf die Anzahl der Ecken in einem Kreis vom Radius r. Zum Beispiel hat Z genau 2r+1 Ecken in einem Ball vom Radius r, das Volumen wächst also linear. In Z2 sind es (ohne genau nachzuzählen) offensichtlich weniger als (2r+1)2 Ecken in einem Ball vom Radius r, das Volumen wächst also quadratisch. Dagegen ist in Z3 das Volumenwachstum kubisch und in der Fundamentalgruppe der Brezel sogar exponentiell.)

Die einzigen Gruppen G mit quadratischem Volumenwachstum sind Gruppen G, die (evtl. nach Kürzen einer endlichen Gruppe3) isomorph zu 0, Z oder Z2 sind. (Das folgt aus einem Satz von Gromov.)
Das sind dann also auch die einzigen Gruppen mit Rückkehrwahrscheinlichkeit 1.
Zurückübersetzt in das ursprüngliche geometrische Problem:
in der Ebene ist die Brownsche Bewegung rekurrent, d.h. man kehrt mit Wahrscheinlichkeit 1 zum Ausgangspunkt zurück (weil dies für Z2 der Fall ist)
im dreidimensionalen Raum ist die Brownsche Bewegung nicht rekurrent (weil für Z3 die Rückkehrwahrscheinlichkeit nicht 1 ist)
in der hyperbolischen Ebene ist die Brownsche Bewegung nicht rekurrent (weil für die Fundamentalgruppe der Brezel die Rückkehrwahrscheinlichkeit nicht 1 ist).

1 Wobei es eigentlich egal ist, ob man den Schlüssel wiederfindet. Man kommt ja auch nie zu der Tür zurück, zu der der Schlüssel gehört.

2 Varopoulos, Saloff-Coste, Coulhon: Analysis and Geometry on Groups

3 Genauer: es gibt eine exakte Sequenz 1 -> N -> G -> F -> 1, wobei F eine endliche Gruppe und N entweder 0 oder Z oder Z2 ist.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85