[JoGu]

Kryptologie

Die mittlere Zeichenkoinzidenz zweier stochastischer Sprachen

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Für stochastische Sprachen L, M ⊆ Σ* mit Buchstabenhäufigkeiten qs bzw. ps für s ∈ Σ wird die mittlere Zeichenkoinzidenz von Texten der Länge r betrachtet:

[Formel]

Satz. Die mittlere Zeichenkoinzidenz der stochastischen Sprachen L und M ist asymptotisch gleich

[Formel]

Der Beweis folgt unten.


Deutung

Die Zeichenkoinzidenz genügend langer gleichlanger Texte aL und bM ist ungefähr

κ(a,b) ≈ ∑s∈Σ psqs.
Das stimmt überein mit der intuitiven Vorstellung, wie wahrscheinlich das Auftreten von Koinzidenzen (Zwillingspaaren) ist.

Spezialfälle

1.) Sei L = Σ* mit den Buchstabenhäufigkeiten qs = 1/n, und M habe die Buchstabenhäufigkeiten ps. Dann ist

κMΣ* = ∑s∈Σ ps/n = 1/n.
Das deutet man so:
κ(»sinnvoller Text«, »zufälliger Text«) ≈ 1/n.

2.) Sei L = M. Dann erhält man die Formel

κMM = ∑s∈Σ ps2.
Das deutet man so:
κ(»sinnvoller Text«, »sinnvoller Text«) ≈ ∑s∈Σ ps2.

3.) Sei L = M(q) = {a(q) | aM} ⊆ Σ*; L besteht also aus den um q Stellen zyklisch verschobenen Texten. Dann ist mit M auch L stochastisch, und zwar mit den gleichen Buchstabenhäufigkeiten. Also ist

κLM = ∑s∈Σ ps2.
Für die Texte aM bilden die Paare (a,a(q)) allerdings keine »repräsentative« Stichprobe aus L×M. Nimmt man aber an, dass a(q) »unabhängig« von a ist - was bei natürlichen Sprachen schon bei q ≥ 2 empirisch möglich ist - so erhält man die Näherungsformel
κq(a) ≈ ∑s∈Σ ps2.


Ein Hilfssatz

Hilfssatz. Sei M eine stochastische Sprache. Dann gilt für die mittlere Abweichung für alle Buchstaben s ∈ Σ:

[Formel]

Beweis. Sei ε > 0 gegeben und r so groß, dass

a) r ≥ 4 × #J/ε,

b) |μsj(r) - ps| < ε/2 für alle j ∈ [0 … r]-J.

Für jJ ist sicher |μsj(r) - ps| ≤ |μsj(r)| + |ps| ≤ 2. Also folgt:

[Formel]

Bemerkung.

[Formel]
ist die mittlere Häufigkeit von s in Texten der Länge r. Dafür gilt also:

Korollar. limr→∞ μs(r) = ps.


Der Beweis des Satzes

[Formel]

[Formel]

[Formel]

[Formel]

Der zweite und dritte Summand konvergieren nach dem Hilfssatz gegen 0, der vierte konvergiert ebenfalls gegen 0, da |εsjηsj| ≤ 1. Also konvergiert die Summe gegen ∑s∈Σ psqs.♦


Autor: Klaus Pommerening, 5. März 2000; letzte Änderung: 6. März 2000.