Cryptography Reference
In-Depth Information
t
0
1
2
3
4
5
6
...
10
...
20
p
1
1
0,00
0,18
0,12
0,12
0,11
0,10
...
0,10
...
0,10
p
2
0
0,20
0,50
0,61
0,68
0,72
0,74
...
0,76
...
0,76
p
3
0
0,80
0,32
0,27
0,20
0,17
0,16
...
0,14
...
0,14
Nach dem zehnten Übergang ändert sich die Verteilung der Zustandswahr-
scheinlichkeiten (bei einer Genauigkeit von zwei Dezimalstellen) nicht mehr,
d. h., diese Verteilung entspricht dem
stationären Zustand
der Quelle.
Mit dem Beispiel 2.2.4 haben wir eine wesentliche Eigenschaft der hier betrach-
teten Klasse von MARKOW-Quellen kennengelernt, nämlich die der
Statio-
narität
.
Die meisten dieser stationären Quellen besitzen darüber hinaus die Eigenschaft
der
Ergodizität
. Ohne auf theoretische Grundlagen ergodischer Prozesse nä-
her einzugehen, soll der für uns wesentliche Aspekt hervorgehoben werden:
Bei ergodischen Quellen hängt die Verteilung der stationären Wahrscheinlich-
keiten nur noch von den Übergangswahrscheinlichkeiten und nicht mehr vom
Anfangszustand der Quelle ab.
Wir können uns von dieser wichtigen Eigenschaft leicht überzeugen, indem im
Beispiel 2.2.4 für die Anfangswahrscheinlichkeiten z. B.
(
p
(0)
i
ge-
wählt wird. Deshalb werden die Zustandswahrscheinlichkeiten im stationären
Bereichauchals
ergodische Zustandswahrscheinlichkeiten
bezeichnet.
Wir wollen im Folgenden stets
ergodische MARKOW-Quellen
vorausset-
zen. Dann können die stationären bzw. ergodischen Zustandswahrscheinlich-
keiten
p
i
(=
p
(
x
i
))
auch aus der allgemeinen
Lösung des vollständigen Glei-
chungssystems
(für den stationären Zustand) gewonnen werden:
)=
3
1
3
1
3
⎫
⎬
p
1
=
p
1
p
(
x
1
|x
1
)+
p
2
p
(
x
1
|x
2
)+
...
+
p
N
p
(
x
1
|x
N
)
,
p
2
=
p
1
p
(
x
2
|x
1
)+
p
2
p
(
x
2
|x
2
)+
...
+
p
N
p
(
x
2
|x
N
)
,
.....................................................
p
N
=
p
1
p
(
x
N
|x
1
)+
p
2
p
(
x
N
|x
2
)+
...
+
p
N
p
(
x
N
|x
N
)
,
(2.11)
⎭
mit
p
1
+
p
2
+
...
+
p
N
=1
.
Im Gegensatz zur iterativen Lösung gemäß Gl. (2.10), deren Genauigkeit von
der Anzahl ausgeführter Übergänge bzw. Iterationsschritte abhängt, führt das
Gleichungssystem (2.11) zu exakten Lösungen.
Für die
binäre MARKOW-Quelle
(
N
=2
) erhalten wir aus Gl. (2.11) die
stationären Zustandswahrscheinlichkeiten
p
(
x
1
|
x
2
)
p
(
x
2
|
x
1
)
p
1
=
, p
2
=
mit
p
1
+
p
2
=1
.
p
(
x
2
|
x
1
)+
p
(
x
1
|
x
2
)
p
(
x
2
|
x
1
)+
p
(
x
1
|
x
2
)
