<<

. 36
( 60 .)



>>

in 2 zu sein. Nehmen wir 20 Schritte, so erhalten wir den komplizierten Ausdruck:
20 « 304 686 352 736 285 456 998 388 430 463 114 258 684 713 561 
«1 1
0
2 2 1218 719 480 020 992 1218 719 480 020 992 304 679 870 005 248
 1 0 2  =  456 998 388 430 463 685 601 424 167 221 6347 031 550 313 
.
3 3 1828 079 220 031 488 1828 079 220 031 488 16 926 659 444 736
021 114 258 684 713 561 6347 031 550 313 42 847 817 108 965
3 3 457 019 805 007 872 16 926 659 444 736 114 254 951 251 968

Nach Rundung ergibt sich jedoch ein ganz einfacher Ausdruck:
20 «
«1 1 1 3 3
« 
0 0.250 01 0.374 98 0.375 01
2 2 4 8 8
1 0 2 1 3 3
 0.249 99 0.375 04 0.374 97   .
3 3 4 8 8
021 1 3 3
0.250 01 0.374 97 0.375 02
3 3 4 8 8

¨
Wir werden sp¨ter verstehen, wieso die Ubergangswahrscheinlichkeiten nach vie-
a
len Iterationen so einfach werden.

8.1.2 Irrfahrten auf Gruppen
G sei eine endliche Gruppe, und µ sei ein sogenannter Wahrscheinlichkeitsvektor
auf G: µ ist einfach eine Abbildung von G nach [0, 1] mit g∈G µ (g) = 1.

Lemma 8.1 P = (pg,h )g,h∈G de¬niert durch

pg,h := µ hg ’1

ist eine stochastische Matrix.

Beweis. Fur jedes feste g ∈ G de¬niert die Abbildung φg : G ’ G, h ’
¨
hg eine Bijektion. In der Tat: φg ist injektiv, denn aus hg ’1 = h g ’1 folgt
’1

h = (hg ’1 ) g = (h g ’1 ) g = h , sowie surjektiv, denn fur jedes h ∈ G gilt h =
¨
’1
hgg = φg (hg) . Daraus folgt

µ hg ’1 =
pg,h = µ (h) = 1
h∈G h∈G h∈G


157
fur jedes g ∈ G.
¨
Man beachte, dass pg,hg = µ (h) ist. µ (h) ist also einfach die Wahrschein-
lichkeit, mit der man von einem beliebigen Element g nach hg springt. Man
bezeichnet das deshalb auch als eine Linksirrfahrt” auf G. Analog kann man die

Rechtsirrfahrt durch pg,h = µ (g ’1 h) de¬nieren.
Als Beispiel betrachten wir ein einfaches Modell dafur, einen Stapel Jass-
¨
karten zu mischen. Naturlich k¨nnen wir (zu mathematischen Zwecken) ein-
o
¨
fach annehmen, dass die Karten von 1 bis 36 durchnumeriert sind. Die Men-
ge I der m¨glichen Reihenfolgen der Karten ist dann einfach die Menge der
o
Permutationen dieser 36 Zahlen. Wir de¬nieren nun eine stochastische Matrix
P = (pσ,π )σ,π∈I , die eines der Standardverfahren modelliert, bei dem man ein-
fach den Stapel 3 Mal uberschl¨gt. (Im Englischen wird das overhand shu¬„ing”
a
¨

¨
genannt. Wir beschr¨nken uns auf dreimaliges Uberschlagen nur der Einfach-
a
heit halber.) Mathematisch l¨sst sich das wie folgt formulieren: Wir w¨hlen
a a
3 Zahlen 1 ¤ m1 < m2 < m3 < 36. Dann de¬nieren wir eine Permutation
πm , m = (m1 , m2 , m3 ) wie folgt: Der Stapel {m3 + 1, 36} wird an die Spitze
verschoben, der Stapel {m2 + 1, m3 } an die zweite Stelle etc, d.h.
··· · · · 36
1
π= .
m3 + 1 · · · 36 m2 + 1 · · · m3 m1 + 1 · · · m2 1 · · · m1
Nun geben wir unter µ jeder dieser speziellen Permutationen die gleiche Wahr-
scheinlichkeit. Es gibt o¬enbar so viele derartige Permutation, wie es M¨glich-
o
35 35·34·33
keiten gibt, 3 Zahlen aus den Zahlen 1, . . . , 35 auszuw¨hlen, also 3 = 6 =
a
6545. Wir de¬nieren daher µ (π) = 1/6545, falls π von dieser Form ist, und an-
dernfalls µ (π) = 0. pσ,πσ = µ (π) gibt dann einfach die Wahrscheinlichkeit an,
mit der man von der Permutation σ zur Permutation πσ gelangt.
Man beachte ubrigens, dass es gigantisch viele Permutationen von 36 Elemen-
¨
ten gibt, n¨mlich
a
36! = 371993326789901217467999448150835200000000.
Rechnet man das Alter des Universums zu 10 Milliarden Jahren, so ist das 1024
mal das Alter des Universums in Sekunden. Trotz dieser unvorstellbar grossen
Zahl ist es das Traumziel” des Kartenmischers, nach einigen wenigen Iterationen

des Mischvorgangs jede dieser M¨glichkeiten mit etwa gleicher Wahrscheinlichkeit
o
zu erhalten. Fur eine wirklich gute Durchmischung in diesem Sinne ist overhand
¨

shu¬„ing” nicht besonders gut geeignet. Man wurde ca. 50 Iterationen ben¨ti- o
¨
gen. Das unter Pokerspielern ublichere ri¬„e shu¬„ing” ist wesentlich besser und
¨

fuhrt nach ca. 7 Iterationen (bei 52 Karten) zum Ziel. Wir werden hier jedoch
¨
nachweisen k¨nnen, dass der Mischvorgang im Prinzip“ zum Ziel fuhrt: dass
o ¨

n¨mlich nach n-facher Iteration fur n ’ ∞ sich asymptotisch die Gleichvertei-
a ¨
lung einstellt.
Als weiteres Beispiel betrachten wir noch die abelsche Gruppe (Zn , +) . Ist
µ (1) = µ (’1) = 1/2, µ (i) = 0 fur alle anderen Elemente, so gilt einfach pij = 1/2
¨

158
fur j = i ± 1, und 0 sonst. Dieses Beispiel konnen wir auch als Irrfahrt auf
¨ ¨
einem Graphen au¬assen: Als Eckpunktmenge nehmen wir Zn , und {i, i + 1}
sind jeweils durch Kanten verbunden. Bei einer anderen Wahl von µ ist dies
jedoch i.allg. nicht mehr moglich (z.B. fur µ (1) = p, µ (’1) = 1 ’p und p = 1/2).
¨ ¨

8.1.3 Gittermodelle der statistischen Physik
Wir betrachten ein ganz einfaches 1-dimensionales Modell der statistischen Phy-
sik, das sogenannte eindimensionale Ising-Modell. Allen Punkten i eines ein-
dimensionalen Gitters {1, . . . , n} ordnen wir sogenannte Spinvariablen” σi zu.

Diese Spins k¨nnen up”, d.h. σi = +1, oder down”, d.h. σi = ’1 sein. Wir
o
” ”
haben mathematisch also einfach eine Folge σ1 , . . . , σn von ±1-Gr¨ssen.
o
Wir suchen nun ein Modell, bei dem sich benachbarte Spins beein¬‚ussen. In
der Physik wird das durch eine Energiefunktion H auf den Spinkon¬gurationen
beschrieben. Wir nehmen an, dass die Wechselwirkung anziehend, im physika-
lischen Jargon ferromagnetisch” ist: Haben benachbarte Spins die gleiche Aus-

richtung, so hat die Kon¬guration eher tiefe Energie. Die einfachste M¨glichkeit,
o
dies zu realisieren, ist durch folgende Energiefunktion gegeben:
n’1
H (σ) := ’J σi σi+1 ,
i=1

wobei J die Wechselwirkungsenergie ist. Nach einem fundamentalen Prinzip der
statistischen Physik stellt sich bei einer Temperatur T > 0 (naturlich in Grad
¨
Kelvin gerechnet) die folgende Gleichgewichtsverteilung ” die sogenannte Gibbs-
Verteilung ” auf den Spinkon¬gurationen σ = (σ1 , . . . , σn ) ein
1
GT (σ) := exp ’ H (σ) Zn (T ) .
kT
Dabei ist k ein physikalische Konstante, die sogenannte Boltzmann-Konstante,
und
1
exp ’ H (σ)
Zn (T ) :=
kT
σ
ist die sogenannte Zustandssumme. Man beachte, dass σ GT (σ) = 1 ist. Ferner
ist naturlich GT (σ) > 0 fur alle σ. Wir k¨nnen die GT (σ) daher als Wahrschein-
o
¨ ¨
lichkeiten interpretieren. Es sind die Wahrscheinlichkeiten, mit denen sich das
System bei Temperatur T in der Kon¬guration σ be¬ndet. Diese Wahrschein-
lichkeiten sind o¬enbar desto gr¨sser, je st¨rker die Kon¬guration σ ausgerichtet
o a
ist, d.h. je mehr Paare (i, i + 1) es gibt mit σi = σi+1 . Wir setzen β := J/kT .
Kleine β entsprechen dann hoher Temperatur und umgekehrt. Man beachte nun,
dass sich exp [’βH (σ)] wie folgt schreiben l¨sst:
a
n’1
exp [’βH (σ)] = Aβ (σi , σi+1 ) ,
i=1


159
wobei Aβ = (Aβ (i, j))i,j=±1 die folgende Matrix ist:

eβ e’β
∈ M + (2)
Aβ :=
e’β eβ

Dies ist die sogenannte Transfermatrix”.

Von fundamentaler Bedeutung in der statistischen Physik ist das Verhalten
der sogenannten freien Energie im Limes n ’ ∞.
1
f (β) := lim log Zn (β) .
n’∞ n

Nun gilt jedoch
An’1 (σ1 , σn ) ,
Zn (β) = (8.1)
β
σ1 ,σn =±1

so dass wir wieder darauf stossen, die Potenzen einer positiven Matrix zu berech-
nen. Wir werden f (β) etwas sp¨ter berechnen.
a

8.2 Irreduzibilit¨t, Periodizit¨t
a a
Wir betrachten in diesem Abschnitt eine Matrix A ∈ M + (n) , A = (aij )i,j∈I . Die
(n)
n-te Potenz bezeichnen wir mit An = aij . Wir fuhren einige Notationen
¨
i,j∈I
ein. Seien i, j ∈ I, n ∈ N0 . Wir schreiben:
n Def (n)
i ’’ j ⇐’ aij > 0,

Def n
i ’’ j ⇐’ ∃n ∈ N0 mit i ’’ j,
Def
i ∼ j ⇐’ i ’’ j und j ’’ i.
n m n+m
Lemma 8.2 a) i ’’ j, j ’’ k =’ i ’’ k.
b) i ’’ j, j ’’ k =’ i ’’ k.
¨
c) ∼ ist eine Aquivalenzrelation auf I.
(n) (m)
Beweis. a) Aus aij > 0 und ajk > 0 folgt

(n+m) (n) (m) (n) (m)
ais ask ≥ aij ajk > 0.
aik =
s∈I

b) folgt sofort aus a).
(0)
c) Re¬‚exivit¨t folgt aus aii = 1 > 0. Die Symmetrie folgt aus der De¬nition.
a
Die Transitivit¨t folgt aus b).
a



160
De¬nition 8.1 A heisst irreduzibel, wenn alle Paare i, j ∈ I ¨quivalent sind,
a
(n)
d.h. wenn fur i, j ∈ I stets ein n ∈ N0 existiert mit aij > 0.
¨
n
Ist i ∈ I, so betrachten wir die Menge “i := n ∈ N : i ’’ i . Man beachte,
dass 0 ∈ “i (N := {1, 2, 3, . . .}). π (i) := ggT (“i ) ist die sogenannte Periode
von i. Ist “i = …, so setzen wir π (i) := ∞.

Lemma 8.3 Ist π (i) < ∞, so existiert ein n0 ∈ N mit nπ (i) ∈ “i fur alle
¨
n ≥ n0 .

Beweis. Lemma 8.2 a) zeigt, dass “i abgeschlossen unter der Addition ist:
Sind n, m ∈ “i , so gilt n + m ∈ “i . Wir zeigen: Ist “ eine beliebige nichtleere

<<

. 36
( 60 .)



>>