std.theorem123 — das 123-Theorem

Das 123-Theorem (Alon/Yuster 1995) begrenzt, wie stark sich die Nähewahrscheinlichkeit zweier unabhängiger, identisch verteilter Zufallsvariablen bei größerem Abstand steigern kann: 

P(|X - Y| <= 2)  <  3 * P(|X - Y| <= 1)

allgemein, für 0 < a < b:
P(|X - Y| <= b)  <  (2 * ceil(b/a) - 1) * P(|X - Y| <= a)

Die Ungleichung ist strikt, und die Konstante lässt sich nicht verbessern: sie wird beliebig genau erreicht, aber nie angenommen. Genau das macht sie als Prüfung brauchbar — wer eine Schätzung hat, die die Schranke erreicht oder überschreitet, hat einen Fehler in der Schätzung, kein Gegenbeispiel zum Theorem.

Seit lyxc 1.1.13B. → Units · std.math · std.alloc

1. Funktionen

Funktion Bedeutung
T123NahePaarStichprobe(data, n, t): f64 P(|X−Y| ≤ t) für eine Stichprobe: data zeigt auf n aneinandergereihte f64, jeder Wert trägt 1/n
T123NahePaar(werte, gewichte, n, t): f64 dasselbe für eine gewichtete Verteilung; die Gewichte dürfen um höchstens 1e-9 von 1 abweichen
T123Schranke(a, b): f64 2 * ceil(b/a) − 1 — für a=1, b=2 ergibt das die namensgebende 3
T123VerhaeltnisStichprobe(data, n, a, b): f64 P(≤b) / P(≤a) — die Zahl, die das Theorem begrenzt
T123VerhaeltnisGewichtet(werte, gewichte, n, a, b): f64 dasselbe für die gewichtete Form
T123Gilt(werte, gewichte, n): bool · T123GiltStichprobe(data, n): bool der Fall a=1, b=2
T123GiltAllgemein(werte, gewichte, n, a, b): bool freie Wahl von a und b
T123Fehlerwert(): f64 · T123IstFehler(x): bool NaN als Fehlerwert erzeugen und erkennen

2. Beispiel

import std.theorem123;
import std.alloc;

fn main(): int64 {
    var n: int64 := 5;
    var data: int64 := alloc(n * 8);
    var i: int64 := 0;
    while (i < n) {
        pokef64(data + i * 8, (i as f64) * 0.75);
        i := i + 1;
    }
    Print("P(|X-Y| <= 1) = "); PrintF64(T123NahePaarStichprobe(data, n, 1.0));
    Print("P(|X-Y| <= 2) = "); PrintF64(T123NahePaarStichprobe(data, n, 2.0));
    Print("Verhaeltnis    = "); PrintF64(T123VerhaeltnisStichprobe(data, n, 1.0, 2.0));
    Print("Schranke(1,2)  = "); PrintF64(T123Schranke(1.0, 2.0));
    if (T123GiltStichprobe(data, n)) { PrintLn("Theorem haelt"); }
    free(data, n * 8);
    return 0;
}


P(|X-Y| <= 1) = 0.520000
P(|X-Y| <= 2) = 0.760000
Verhaeltnis    = 1.461538
Schranke(1,2)  = 3.000000
Theorem haelt

3. Drei Punkte, die man wissen muss

  • Die Diagonale zählt mit. Gezählt werden alle n×n geordneten Paare, i == j eingeschlossen. Das ist die Definition: X und Y sind unabhängig, sie dürfen denselben Wert treffen. Wer die Diagonale weglässt, rechnet „zwei Züge ohne Zurücklegen„ — eine andere Größe, und für kleine n eine deutlich andere.
  • Die Schranke springt. Sie hängt nur davon ab, wie oft a in b passt, nicht vom genauen Verhältnis: für b/a knapp über einer ganzen Zahl springt sie um 2 nach oben. Kein Rundungsfehler, sondern die Aussage.
  • Ein false ist eine Aussage über die Eingabe, nicht über das Theorem. Das Theorem ist bewiesen; wer hier durchfällt, hat falsche Gewichte, vertauschte Werte oder einen zu kurzen Puffer. Deshalb meldet die Unit den Fall zusätzlich auf stderr, statt nur false zu liefern. Fehler kommen als NaN zurück (T123IstFehler).
 
Warum der Fehlerwert eine Funktion ist und keine con. Eine Rechnung im Initialisierer einer f64-con wird still falsch übersetzt: 0.0 / 0.0 kommt als 0.0 an, 0.0 - 0.5 als -8.0, 2.0 * 3.0 als 0.0 (gemessen mit 1.1.13A, #1853). Reine Literale stimmen. T123Fehlerwert() rechnet das NaN deshalb aus Variablen — der Weg, der nachweislich trägt. Ein -1 als Fehlerwert wäre keine Alternative: es ist eine gültige Zahl, und 0 beziehungsweise 1 würden als „nie“ und „immer„ gelesen — beides plausibel, beides falsch.

Letzte Aktualisierung: 2026-08-30 — Seite neu angelegt; Signaturen aus std/theorem123.lyx, Beispiel gegen lyxc 1.1.14A gebaut und gelaufen.

Codebeispiele geprüft: gegen lyxc 1.2.5C übersetzt (Prüflauf 2026-09-08 über die gesamte Doku: 574 Vollprogramme, 0 echte Fehler; zusätzlich 5159 Aufrufe gegen die pub fn-Signaturen in aurum/std gehalten, 0 Abweichungen).