<<

. 37
( 60 .)



>>

Teilmenge von N mit dieser Eigenschaft und π := ggT (“) , so gilt nπ ∈ “, wenn n
gross genug ist. (Die genaue Herkunft von “ spielt weiter keine Rolle; wir lassen
deshalb den Index i weg).
Zun¨chst zeigen wir, dass eine endliche Teilmenge “ ‚ “ existiert mit ggT(“ )
a
= ggT(“) = π. Dies sieht man wie folgt ein: Sei “n = “ © {1, . . . , n} . Da “ nicht
leer ist, ist “n nicht leer, wenn n gross genug ist. Sei gn := ggT (“n ) . Da gn+1 alle
Elemente in “n+1 teilt, teilt es auch alle Elemente in “n , und somit teilt gn+1 auch
gn . Insbesondere folgt gn ≥ gn+1 ≥ gn+2 ≥ . . . . Nun kann aber nur endlich oft
ein striktes Ungleichheitszeichen stehen, und somit existiert ein m mit g = gm
fur alle ≥ m. Daraus folgt aber sofort, dass gm der gr¨sste gemeinsame Teiler
o
¨
aller Elemente in “ ist, also gm = π.
Sei nun “m = {n1 , n2 , . . . , nk } , d.h. π = ggT (n1 , . . . , nk ) . Dann existieren
Zahlen l1 , . . . , lk ∈ Z, so dass π = k li ni ist (vgl. Abschnitt 6.4.3). Weil alle
i=1
nj Vielfache von π sind, existiert ein K ∈ N mit
k
nj = Kπ.
j=1

Sei
L := (K ’ 1) max |lj | , und n0 := KL.
j

Sei n ≥ n0 . Division durch K mit Rest ergibt

n = RK + r, R ≥ L, 0 ¤ r ¤ K ’ 1.

Demzufolge gilt
k k
nπ = RKπ + rπ = Rnj + r lj nj
j=1 j=1
k
= (R + rlj ) nj .
j=1



161
Wegen R ≥ L und der De¬nition von L folgt aber R + rlj ≥ 0, d.h. R + rlj ∈
N0 fur alle j. Aus der Abgeschlossenheit unter der Addition folgt dann aber
¨
k
j=1 (R + rlj ) nj ∈ “. Somit ist nachgewiesen, dass fur alle n ≥ n0 die Zahl nπ
¨
in “ ist.

Proposition 8.1 Ist i ∼ j so gilt π (i) = π (j) .

Beweis. Ist i = j, so folgt naturlich π (i) = π (j) . Wir k¨nnen daher vor-
o
¨
n
aussetzen, dass i = j gilt. Per De¬nition existieren dann n, m ∈ N mit i ’’ j
m n+m n+m
und j ’’ i. Wegen Lemma 8.2 a) folgt dann i ’’ i, j ’’ j. Somit sind
n0 π(j) (n0 +1)π(j)
π (i) , π (j) < ∞. Nach Lemma 8.3 existiert n0 ∈ N mit j ’’ j und j ’’ j.
Nochmals 8.2 a) angewandt ergibt:
n+n0 π(j)+m n+(n0 +1)π(j)+m
’’ ’’
i i, i i.

Daraus folgt π (i) |n+n0 π (j)+m und π (i) |n+(n0 + 1) π (j)+m, d.h. π (i) |π (j) .
Analog zeigt man π (j) |π (i) . Daher gilt π (i) = π (j) .
Diese Proposition besagt also, dass die Periode eine Klassengr¨sse unter der
o
¨ ¨
obigen Aquivalenzrelation ist, d.h. die Periode ist auf jeder Aquivalenzklasse eine
konstante Funktion. Insbesondere gilt fur jede irreduzible Matrix, dass alle Ele-
¨
mente von I dieselbe Periode haben. Man spricht dann einfach von der Periode
der Matrix.

De¬nition 8.2 Eine irreduzible Matrix A ∈ M + (n) heisst aperiodisch, wenn
die Periode der Matrix 1 ist.

Wir zitieren ohne Beweis (der nicht sehr schwierig, aber etwas l¨nglich und
a
nicht allzu interessant ist), den folgenden Satz:

Satz 8.1 Sei A irreduzibel mit Periode p ≥ 2. Dann existiert eine Zerlegung von
I in p disjunkte Teilmengen:

I = I1 ∪ . . . ∪ Ip , Ii © Ij = … f¨r i = j,
u

mit der folgenden Eigenschaft: Fur alle k ∈ {1, . . . , p} und alle i ∈ Ik gilt
¨
1
j ∈ I : i ’’ j ‚ Ik+1 (mit der Konvention Ip+1 := Ii ). In Worten: Von
Ik aus kann man in einem Schritt nur nach Ik+1 gelangen.
¨
Die Zerlegung {Ik : 1 ¤ k ¤ p} ist die Zerlegung von I nach Aquivalenzklassen
bezuglich der Matrix Ap .
¨

Wir diskutieren noch kurz die Beispiele aus Abschnitt 8.1. Die Irrfahrt auf
Graphen ist genau dann irreduzibel, wenn der Graph zusammenh¨ngend ist.
a


162
De¬nition 8.3 Ein Graph G = (E, K, •) heisst nicht zusammenh¨ngend, a
wenn es eine echte nichtleere Teilmenge A ‚ E gibt, sodass keine Ecke in A mit
einer Ecke ausserhalb A durch eine Kante verbunden ist. Ein Graph der nicht
nicht zusammenh¨ngend ist heisst zusammenh¨ngend.
a a

Proposition 8.2 Die stochastische Matrix aus Abschnitt 8.1.1 ist genau dann
irreduzibel, wenn G zusammenh¨ngend ist.
a

Der sehr einfache Beweis sei dem Leser uberlassen.
¨
Periodizi¨t oder Aperiodizit¨t fur Irrfahrten auf Graphen zu entscheiden, ist
a a¨
i.allg. etwas schwieriger. Es ist jedoch evident, dass wenn in einem zusam-
menh¨ngenden Graphen auch nur eine Ecke existiert, die mit sich selbst ver-
a
bunden ist, die Matrix dann aperiodisch ist. Fur eine Ecke e, die mit sich selbst
¨
verbunden ist, gilt n¨mlich pe,e > 0 und damit π (e) = 1. Wenn der Graph zu-
a
sammenh¨ngend ist, folgt daraus jedoch, dass π (e) = 1 fur alle e ist. Irreduzible
a ¨
Irrfahrten auf Graphen sind jedoch aperiodisch oder haben Periode 2. Es gilt
(2)
n¨mlich stets pe,e > 0 ” pe ,e > 0. Daraus folgt sofort pe,e > 0.
a
Das Beispiel des overhand shu¬„ing“ in Abschnitt 8.1.2 ist irreduzibel und

aperiodisch. Der Leser m¨ge sich das selbst uberlegen. Wir betrachten noch
o ¨
das Beispiel der Irrfahrt auf (Zn , +) . Die zugeh¨rige Matrix ist o¬ensichtlich
o
irreduzibel, denn man kommt mit positiver Wahrscheinlichkeit von jedem Punkt
(2)
zu jedem anderen Punkt nach genugend vielen Iterationen. Ebenfalls gilt pi,i >
¨
(n)
0 fur jedes i. Die Periode ist somit 1 oder 2. Ferner ist pi,i > 0, weil man
¨
in n Schritten einmal um den Kreis“ laufen kann. Ist n ungerade, so ist die

Matrix also aperiodisch (wegen ggT (n, 2) = 1). Ist jedoch n gerade, so kann man
die Elemente von Zn in die Gruppen der geraden und der ungeraden Elemente
aufteilen. O¬ensichtlich kann man dann in einem Schritt nur von der geraden
Gruppe in die ungerade und von der ungeraden Gruppe in die gerade wechseln.
Daraus folgt sofort, dass die Periode gleich 2 ist.

8.3 Der Perron-Frobenius Eigenwert
Wir fuhren die folgenden Bezeichnungen ein:
¨

D := {z ∈ C : |z| ¤ 1} ,

S := {z ∈ C : |z| = 1} .
Wir ben¨tigen zwei vorbereitende Hilfss¨tze:
o a
n
Lemma 8.4 Seien z1 , . . . , zn ∈ D, »1 , . . . , »n ∈ [0, 1] mit »k = 1, z :=
k=1
n
k=1 »k zk ∈ S. Dann gilt zj = z fur alle j mit »j > 0.
¨



163
Beweis. Wir konnen oBdA annehmen, dass alle »k > 0 sind. Wegen
¨
z ∈ S existiert ein • ∈ [0, 2π) mit z = ei• . Wir setzen zk := e’i• zk . Dann
ist n »k zk = 1. Somit folgt n »k Re (zk ) = 1 oder
k=1 k=1

n
»k (1 ’ Re (zk )) = 0.
k=1

Nun sind jedoch die »k > 0 und die zk haben nach wie vor Betrag ¤ 1. Demzufolge
ist Re (zk ) ¤ 1 oder 1 ’ Re (zk ) ≥ 0. Aus der obigen Gleichung folgt daher
1 ’ Re (zk ) = 0 fur alle k, d.h. Re (zk ) = 1, was wegen zk ∈ D impliziert, dass die
¨
zk alle gleich 1 sind. Das bedeutet aber nichts anderes als zk = ei• = z fur alle
¨
k.

Lemma 8.5 Sei A eine irreduzible aperiodische Matrix ∈ M + (n) . Dann exi-
stiert N ∈ N, sodass alle Matrixelemente von AN strikt positiv sind.

Beweis. Nach Lemma 8.3 existiert fur jedes i ∈ I eine naturliche Zahl ni ,
¨ ¨
(n)
sodass aii > 0 fur alle n ≥ ni gilt. Da I endlich ist, gilt fur n ≥ M := maxi ni :
¨ ¨
(n)
aii > 0 fur alle i ∈ I und n ≥ M. Weiter gilt wegen der Irreduzibilit¨t, dass
a
¨
(kij )
fur i, j ∈ I ein kij ∈ N existiert mit aij > 0. Wieder mit Lemma 8.2 folgt nun
¨
(n) (n)
aij > 0 fur alle n ≥ M + kij . Demzufolge gilt aij > 0 fur alle i, j ∈ I und alle
¨ ¨
n ≥ N := M + maxij kij .
Wir formulieren nun den Hauptsatz der Perron-Frobenius-Theorie, aber zu-
nachst nur fur stochastische Matrizen P = (pij ) . Wenn wir nachfolgend von
¨ ¨
Eigenwerten sprechen, meinen wir immer (moglicherweise) komplexe Eigenwerte.
¨
Ist P stochastisch, so wissen wir, dass 1 ∈ spec (P ) gilt.

Satz 8.2 (Perron-Frobenius, stochastische Matrizen) Sei P eine irreduzi-
ble stochastische Matrix. Dann gilt:
a) Alle (eventuell komplexen) Eigenwerte haben Betrag ¤ 1.
b) 1 ist ein algebraisch (und deshalb auch geometrisch) einfacher Eigenwert.
c) P ist genau dann aperiodisch, wenn 1 der einzige Eigenwert vom Betrag 1
ist.

Beweis. a) Wir fassen P als lineare Abbildung von CI ’ CI auf. Sei
» ∈ specC (P ) . (zi )i∈I , zi ∈ C sei ein Eigenvektor, d.h. es gilt

pij zj = »zi , ∀i ∈ I.
j


Sei i0 so gew¨hlt, dass
a
|zi0 | = max |zi | (8.2)
i




164
gilt. Dann folgt aus der obigen Gleichung

|»| |zi0 | = pi0 j zj ¤ pi0 j |zj |
j j

¤ pi0 j |zi0 | = |zi0 | .
j

Daraus folgt |»| ¤ 1.
b) Wir zeigen zun¨chst, dass 1 geometrisch einfach ist. Sei z ∈ CI ein Eigen-
a
vektor zum Eigenwert 1. Wir w¨hlen wieder i0 mit (8.2). Naturlich muss dann
a ¨
zi0 = 0 gelten, sonst w¨re z der Nullvektor. Wir setzen nun
a
xi := zi /zi0 . (8.3)
Dann ist x = (xi )i∈I ebenfalls ein Eigenvektor zu 1, denn wir haben ja z nur
mit einem Faktor multipliziert. Ferner gilt xi ∈ D fur alle i. Aus der Gleichung
¨
k
x = P x folgt x = P x fur alle k, d.h. insbesondere
¨
(k)
1 = xi0 = pi0 j xj .
j∈I
(k)
Nun gilt aber j pi0 j = 1. Aus Lemma 8.4 folgt daher, dass xj = 1 fur alle j
¨
(k)
mit pi0 j > 0 ist. Wegen der Irreduzibilit¨t existiert jedoch fur jedes j mindestens
a ¨

<<

. 37
( 60 .)



>>