Seltene Ausfälle schätzen verständlich erklärt

Wer ein Netz, das nur selten ausfällt, am Rechner nachspielt, sieht den Ausfall womöglich in keinem einzigen Durchgang. „Seit tausend Durchgängen kein Ausfall“ heißt dann nicht „unmöglich“. Abhilfe: Ausfälle absichtlich häufiger auftreten lassen und die Übertreibung danach wieder herausrechnen. Der Haken: Wer viel zu stark übertreibt, schneidet schlechter ab als ohne Übertreibung.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Nicht gesehen heißt nicht unmöglich

Stellen Sie sich ein Netz vor, etwa Standorte, die durch Straßen oder Leitungen verbunden sind. Jede Verbindung kann ausfallen, jede für sich und ohne die anderen zu beeinflussen. Das Netz als Ganzes gilt als ausgefallen, wenn es in getrennte Teile zerfällt, man also nicht mehr von jedem Standort zu jedem anderen kommt. Weil die einzelnen Verbindungen zuverlässig sind, passiert das nur selten. Man möchte trotzdem wissen, wie selten genau, etwa um zu entscheiden, ob sich eine zusätzliche Reserveverbindung lohnt.

Der naheliegende Weg ist Ausprobieren am Rechner: Man spielt das Netz tausend Mal durch, würfelt jedes Mal aus, welche Verbindungen ausfallen, und zählt die Durchgänge, in denen das Netz zerfällt. Ist das so selten, dass in tausend Durchgängen womöglich kein einziger solcher Ausfall vorkommt, lautet das Ergebnis „null“. „Kein Ausfall in tausend Durchgängen“ heißt aber nur: nicht gesehen. Es heißt nicht: unmöglich.

Zu dieser Seite gehört eine Demo, ein Programm zum Ausprobieren im Browser. Der erste Knopf am Ende dieses Teils öffnet sie; zum Verstehen brauchen Sie sie nicht. Spielt man dort ein erfundenes Beispielnetz mehrfach mit je tausend Durchgängen durch, sieht die Mehrzahl der Wiederholungen keinen einzigen Ausfall.

Warum passiert das?

Ein seltenes Ereignis zu zählen ist wie eine Stecknadel im Heuhaufen zu suchen: Man muss so lange würfeln, bis man sie einmal findet. Je seltener das Ereignis, desto länger dauert die Suche, und die Zahl der Durchgänge, die für ein verlässliches Ergebnis nötig ist, wächst mit der Seltenheit.

Wer nur einen oder zwei Ausfälle findet, hat eine wacklige Schätzung: Käme einer hinzu oder fiele einer weg, sähe das Ergebnis anders aus.

Was hilft: Ausfälle absichtlich häufiger machen

Man tut beim Würfeln so, als wären die Verbindungen unzuverlässiger, als sie sind. Dann zerfällt das Netz so oft, dass man genug Ausfälle zum Zählen hat. Damit das Ergebnis nicht verfälscht wird, rechnet man die Übertreibung wieder heraus: Jeder Durchgang bekommt ein Gewicht, das sagt, wie viel er in der echten, zuverlässigen Welt zählen würde. Je mehr ausgefallene Verbindungen ein Durchgang enthält, desto stärker hat die Übertreibung ihn begünstigt, und desto kleiner ist sein Gewicht. Fachleute nennen das Importance Sampling; für die Übertreibung sagen sie Kippung.

Ein Vergleich aus der Umfrageforschung: Will man etwas über eine kleine Gruppe wissen, befragt man absichtlich mehr ihrer Mitglieder, als es ihrem Anteil entspricht, und rechnet die Antworten danach auf den wahren Anteil zurück. Mit richtigen Gewichten verfälscht das den Durchschnitt nicht.

Der Gewinn wächst mit der Seltenheit. Die Demo rechnet das für ein erfundenes Beispielnetz genau aus. Fällt dort jede Verbindung nur mit einer Wahrscheinlichkeit von eins zu tausend aus, braucht einfaches Zählen Millionen Durchgänge, bis das Ergebnis von Wiederholung zu Wiederholung nur noch um etwa ein Zehntel des wahren Wertes schwankt. Mit gut gewählter Übertreibung reichen dafür gut zehntausend.

Der Haken: Zu viel Übertreiben schadet

Die passende Stärke der Übertreibung hängt von der empfindlichsten Stelle des Netzes ab: der kleinsten Gruppe von Verbindungen, deren gemeinsamer Ausfall das Netz trennt (Fachleute sagen kleinster Schnitt). Sind die echten Ausfälle selten, ist die Übertreibung in der Demo am besten, wenn durchschnittlich je Durchgang so viele Verbindungen ausfallen, wie diese Gruppe Mitglieder hat. Der Grund: Ein seltener Netzausfall entsteht dann fast nur über diese kleinste Gruppe, und genau solche Durchgänge soll die Übertreibung häufig machen. Weiß man nicht, wo diese Gruppe liegt, etwa in einem großen Netz, muss man die Stärke aus den Durchgängen selbst lernen; das zeigt die Demo nicht.

Übertreibt man weit über diese Stärke hinaus, wird das Ergebnis schlechter, als wenn man gar nicht übertrieben hätte. Im Beispielnetz der Demo hilft eine etwas zu starke Übertreibung noch; erst eine weit zu starke schadet. Das Netz zerfällt dann zwar in fast jedem Durchgang, aber die Gewichte werden so ungleich, dass einzelne Durchgänge das Ergebnis fast allein bestimmen.

Woran man merkt, dass die Gewichte nicht mehr verlässlich sind

Eine ehrliche Kontrolle fragt: Wie viele der Durchgänge zählen wirklich mit? Haben alle Durchgänge ähnliche Gewichte, zählen alle mit. Hat ein einzelner Durchgang fast das ganze Gewicht, zählt praktisch nur er, gleichgültig, wie viele Durchgänge es insgesamt waren, und die Schätzung ist nur so verlässlich wie dieser eine. Fachleute nennen diese Zahl effektive Stichprobengröße; die Demo zeigt sie an.

Eine gängige Warnzahl für aus dem Ruder laufende Gewichte schlägt in der Demo selbst bei der besten Übertreibung Alarm, wie ein Rauchmelder, der schon bei einer Kerze klingelt. Aussagekräftig ist sie hier wohl nicht: Sie setzt viele fein abgestufte große Gewichte voraus, hier gibt es aber nur wenige verschiedene Werte. Die bessere Kontrolle bleibt die Zahl der mitzählenden Durchgänge.

Worauf Sie bei solchen Rechnungen achten können

Steht in einem Bericht „kein Ausfall in der Simulation“, fragen Sie, wie viele Durchgänge es waren und wie selten das Ereignis ist, also ob man bei dieser Zahl von Durchgängen überhaupt einen Ausfall erwarten durfte. Wurde mit Übertreibung gerechnet, fragen Sie, wie viele Durchgänge wirklich mitzählen und ob die Rechnung gegen einfaches Würfeln geprüft wurde. Ein Warnzeichen: Wiederholt man die ganze Rechnung mit anderem Zufall, und das Ergebnis springt um ein Vielfaches, sind die Gewichte nicht verlässlich.

Wie ernst ist das Modell zu nehmen?

Die Netze und Ausfallwahrscheinlichkeiten der Demo sind erfunden, und alle Verbindungen fallen gleich selten und unabhängig voneinander aus. Die richtige Antwort ist trotzdem bekannt: Die Netze sind so klein, dass der Rechner alle Kombinationen ausgefallener Verbindungen durchgehen kann; daran misst die Demo jede Schätzung. Bei großen Netzen geht das nicht mehr. Die Aussage zur Warnzahl gilt nur für die Gewichte dieser Demo und ihre eigene Umsetzung.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

• Ereignis: \(A\) = das Netz hängt nicht zusammen (Netzausfall). Jede der \(m\) Kanten fällt unabhängig mit Wahrscheinlichkeit \(q\) aus (Kantenausfall); \(P\) ist die Wahrscheinlichkeit von \(A\). Netze: Knotengitter 3×3 und 3×4 (3 mal 4 Knoten, 17 Kanten) und die Hantel (zwei Dreiecke, eine Brücke). Alle \(2^m\) Kantenmengen werden aufgezählt, \(P\), zweites Moment und \(\mathrm{CV}^2\) sind also ohne Zufallsfehler bekannt („exakt“).
• Importance Sampling: Kippung (Tilting) heißt: In der Hilfsverteilung fällt jede Kante mit erhöhter Wahrscheinlichkeit \(q'\) statt \(q\) aus, ein \(q'\) für alle Kanten. Eine Ziehung mit \(f\) Kantenausfällen hat das Gewicht \(w(f) = (q/q')^f\,((1-q)/(1-q'))^{m-f}\); der Schätzer ist das Mittel von \(\mathbf 1[A]\,w\) und für \(0 < q' < 1\) erwartungstreu. Einfaches Ziehen ist \(q' = q\).
• Diagnose: ESS (unten) und Pareto-\(\hat k\) (eigene Umsetzung nach Zhang und Stephens in der Form von Vehtari et al.): eine verallgemeinerte Pareto-Verteilung an den größten Gewichten. Marken: wahres \(k \ge 1/2\) heißt unendliche Varianz; \(\hat k\) über 0,7 gilt nach Vehtari et al. als nicht verlässlich (neuere Fassungen: Marke abhängig von der Stichprobengröße; aus dem Gedächtnis, nicht geprüft).
• Methodik: Jede Wiederholung zieht aus einer eigenen festen, reproduzierbaren Zufallszahlenfolge (SplitMix64, aus Schlüssel und Wiederholungsnummer); je Messung 300 bis 400 Wiederholungen.
• Kennzahlen: mediane Abweichung = Median von \(|\hat P/P - 1|\); Überdeckung = Anteil der Wiederholungen, deren Wald-Intervall \(\hat P \pm z\,\mathrm{SE}\) zum Nominalniveau fünfundneunzig Prozent \(P\) enthält (\(\mathrm{SE}\) = Standardabweichung der gewichteten Werte durch \(\sqrt N\)); Gewinn = \(\mathrm{CV}^2\) einfach durch \(\mathrm{CV}^2\) gekippt, das Verhältnis der nötigen Ziehungszahlen.

Die Formeln

Schätzer (eine Ziehung ohne \(A\) trägt null bei):

\[\hat P = \frac1N\sum_i \mathbf 1[A_i]\,w(f_i)\]

Sei \(N_f\) die Zahl der Kantenmengen mit genau \(f\) ausgefallenen Kanten, bei denen das Netz getrennt ist (\(A\) tritt ein). Die Aufzählung liefert dann das zweite Moment und die relative Varianz einer Ziehung (quadrierter Variationskoeffizient):

\[M_2 = \sum_f N_f\,\frac{\bigl[q^f(1-q)^{m-f}\bigr]^2}{q'^f(1-q')^{m-f}},\qquad \mathrm{CV}^2 = \frac{M_2 - P^2}{P^2}\]

Probe: Pfad aus zwei Kanten, \(N_1 = 2\), \(N_2 = 1\), \(q = 1/2\), \(q' = 3/4\) gibt \(M_2 = 7/9\). Für den relativen Fehler \(\varepsilon\) (Standardabweichung von \(\hat P\) durch \(P\)) braucht man \(N = \mathrm{CV}^2/\varepsilon^2\) Ziehungen, für 10 % also \(100\,\mathrm{CV}^2\). Einfaches Ziehen hat \(\mathrm{CV}^2 = (1-P)/P\).

Woher die Schnittregel kommt (Rechnung dieser Seite, eine Näherung): Ist \(s\) die Größe des kleinsten Schnitts, beherrschen für kleine \(q\) die trennenden Mengen der Größe \(s\) sowohl \(P\) als auch \(M_2\). Der Summand \(f = s\) in \(M_2\) ist proportional zu \(1/(q'^s(1-q')^{m-s})\), am kleinsten bei \(q' = s/m\), also wenn im Mittel \(s\) Kanten ausfallen. Bei größerem \(q\) tragen größere Mengen mit, das Optimum liegt höher; gemessen gilt die Regel für \(q \le 0{,}02\). Zum Maßstab (Rechnung dieser Seite): Die Minimalschnitt-Näherung der Fehlerbaum-Praxis, \(P\) etwa Zahl der kleinsten Schnitte mal \(q^s\), gibt im Gitter 3×4 (vier Ecken mit je zwei Kanten) bei \(q\) = 0,01 knapp weniger als das exakte \(P\); Importance Sampling lohnt, wo man die Schnitte nicht kennt.

Effektive Stichprobengröße der Werte \(w_i = \mathbf 1[A_i]\,w(f_i)\):

\[\mathrm{ESS} = (\sum w_i)^2 / \sum w_i^2\]

Mit Erwartungswerten statt Summen folgt \(\mathrm{ESS} \approx N/(1+\mathrm{CV}^2)\) und \(\varepsilon \approx 1/\sqrt{\mathrm{ESS}}\) (Rechnung dieser Seite). Das gilt nur, solange die Stichprobe das zweite Moment trifft, grob für \(N\) groß gegen \(1+\mathrm{CV}^2\). Bei zu starker Kippung bestimmen seltene Ziehungen mit wenigen Ausfällen und riesigem Gewicht \(M_2\); sie fehlen meist in der Stichprobe, und die gemessene ESS liegt weit über dem Formelwert (mindestens eins, sobald ein Ausfall gezogen wird). \(\varepsilon\) ist eine Standardabweichung; der Median von \(|\hat P/P-1|\) ist bei annähernd normalem Schätzer etwa zwei Drittel davon.

Stetiger Begleiter: \(P(X > t)\) für \(X \sim \mathrm{Exp}(1)\), Hilfsverteilung \(\mathrm{Exp}(\theta)\), Gewicht \(e^{-(1-\theta)x}/\theta\). Für \(\theta < 2\) gilt

\[M_2 = e^{-(2-\theta)t}/(\theta(2-\theta))\]

und sonst ist \(M_2\) unendlich. Für \(\theta > 1\) hat der Rand der Gewichte den Index \(\theta/(\theta-1)\), also den Formparameter \(k = (\theta-1)/\theta\); die Varianz ist genau für \(k < 1/2\) endlich.

Befunde

Wo nichts anderes steht: Gitter 3×4, \(q\) = 0,01 (\(P\) = 4,2·10⁻⁴), \(q'\) = 0,12, \(N\) = 1000.

Frage	Befund
Einfaches Ziehen, \(N\) = 1000 (400 Wiederholungen)	65 % der Läufe ohne einen einzigen Netzausfall (exakt \((1-P)^N\) = 0,66), Überdeckung 0,35, mediane Abweichung 100 %.
Standardfall, \(q'\) = 0,12, \(N\) = 1000	Abweichung (Median) 19 %, keine Nullschätzung, Überdeckung 0,92, ESS 12,4 (Formel 12,3), mehr als 50 % Fehler in 6 % der Läufe.
Zu starke Kippung, \(q'\) = 0,5, \(N\) = 1000	mediane Abweichung 98 %, Überdeckung 0,14, Median-ESS 2,9 (Formel 0,04, Grund oben); bei \(q'\) = 0,7 Überdeckung 0,01 bis 0,02.
Falsche Kippung, \(\mathrm{CV}^2\) exakt	\(q'\) = 0,003: 37 104; 0,12: 80,6; 0,3: 399; 0,5: 22 351; 0,7: 2,4·10⁷. Ab etwa \(q'\) ≈ 0,4 schlechter als einfaches Ziehen.
Hantel, \(q'\) = 0,14, \(N\) = 1000	\(\mathrm{CV}^2\) 93,4 → 13,1 (Gewinn 7,2), Abweichung (Median) 8 %, Überdeckung 0,94, ESS 71,2 (Formel 71,1).
Ziehungen für 50 / 20 / 10 / 5 % Fehler, exakt	optimal gekippt 322 / 2014 / 8057 / 32 227; einfach (\(\mathrm{CV}^2\) = 2397) 9589 / 59 934 / 239 737 / 958 946.
Pareto-\(\hat k\) im Netz, \(N\) = 1000	Median 2,6 beim optimalen \(q'\), in 100 % der Läufe über 0,7; Hantel 15,9 (96 % der Läufe über 0,7); \(q'\) = 0,5: 7,3. Beim einfachen Ziehen nicht bestimmbar (gleiche Gewichte).

Optimale Kippung im Gitter 3×4 (exakt):

q	optimales q'	Gewinn
0,1	0,176	2,1
0,05	0,137	3,4
0,02	0,121	10,1
0,01	0,119	29,8
0,005	0,118	101
0,002	0,118	572
0,001	0,118	2210

Bei \(q\) = 0,001: 11 263 statt 24,9 Millionen Ziehungen für 10 % Fehler. Schnittregel: 3×4 2/17 = 0,118; 3×3 (\(q\) = 0,001) 2/12 = 0,167 (gefunden 0,1667); Hantel 1/7 = 0,143 (gefunden 0,1428).

Stetiger Begleiter, \(t\) = 2 (\(P\) = 0,135), \(N\) = 10 000 Ziehungen je Wiederholung, \(\hat k\) als Median:

θ	exaktes k	k̂	CV²	Überdeckung
1,2	0,167	0,18	10,5	0,94
1,5	0,333	0,34	25,8	0,94
1,8	0,444	0,44	100,7	0,93
2,0	0,500	0,50	unendlich	0,92
2,5	0,600	0,58	unendlich	0,85
3,0	0,667	0,60	unendlich	0,80

Ab \(\theta\) = 2 ist die Varianz unendlich; das Wald-Intervall wird dabei nicht entsprechend breiter, nur die Überdeckung sinkt allmählich unter das Nominalniveau. \(\hat k\) folgt hier dem exakten \(k\) und warnt ab 0,5. Optimales \(\theta\) = 0,382 mit \(\mathrm{CV}^2\) = 2,47.

Grenzen und was die Messung zeigt

• Pareto-\(\hat k\) im Netz: Unter den größten \(\min(0{,}2N,\,3\sqrt N)\) Gewichten, an die angepasst wird (bei \(N\) = 1000 höchstens 94), kommen nur etwa sechs verschiedene Werte vor; die Anpassung ist dort entartet und \(\hat k\) nicht aussagekräftig, und eine zweite Anpassung an dieselben Werte belegt keine richtige Umsetzung (nicht gegen das R-Paket loo geprüft). Als Diagnose bleiben im Netz ESS und \(\mathrm{CV}^2\).
• Größere Netze: Bis 17 Kanten ist Aufzählen jeder Schätzung überlegen; ob Gewinn und Schnittregel auf nicht mehr aufzählbare Netze übertragen, misst die Demo nicht (dort muss \(q'\) gelernt werden, je Kante: Folgedemo mit Kreuzentropie).
• Umfang: nur „Netzausfall“ in erfundenen Netzen, unabhängige gleiche Ausfälle; kein selbstnormiertes Importance Sampling, keine Mischungen, kein Vergleich mit Splitting.
• Intervall und Rauschen: Bei wenigen effektiven Ausfällen ist das Wald-Intervall zu schmal, und Messungen (kleines \(N\), kleines \(q\)) rauschen stark; die exakten Zahlen nicht.

Quellen

• Zhang und Stephens (2009): Anpassung der verallgemeinerten Pareto-Verteilung, Grundlage der \(\hat k\)-Berechnung.
• Vehtari et al.: Pareto smoothed importance sampling; Marken 0,5 und 0,7.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/importance-sampling-demo.

Beide Angaben nach der Demo; der Titel bei Vehtari et al. aus dem Gedächtnis, nicht nachgeschlagen.