Monte-Carlo-Schätzung und Varianzreduktion erklärt
Stellen Sie sich vor: Ein kleines Leitungsnetz in Gitterform, in dem Ausfälle selten sind. Wie wahrscheinlich zerfällt es? Sie würfeln tausend Ausfallmuster und zählen, in wie vielen das Netz zerfällt. In der Demo sieht eine solche Stichprobe bei einem sehr stabilen Gitter mit Wahrscheinlichkeit 0,659, also in knapp zwei von drei Fällen, gar keinen Ausfall, und die Schätzung lautet null. Wie genau ist eine Zahl aus Zufallsziehungen, und wie bringt man ihren Fehler bei gleichem Aufwand herunter?
Das ist eine Monte-Carlo-Schätzung: Eine Größe wird nicht ausgerechnet, sondern aus Zufallsziehungen geschätzt, hier als Anteil der Ziehungen, in denen das Netz zerfällt. Dazu gehört eine Fehlerangabe, ein Bereich um die Zahl, der die Wahrheit meist enthalten soll. Wie stark die Schätzung schwankt, misst die Varianz. Die Leitfrage dieser Linie lautet: Wie genau ist eine geschätzte Zahl, wie senkt man ihre Varianz bei gleichem Aufwand, und stimmt die Fehlerangabe danach noch?
Sechzehn Stücke gehen dem nach. Die ersten setzen den Zufall gezielter ein: Sie spiegeln die Zufallszahlen, nutzen beim Vergleich zweier Netzentwürfe dieselben Zahlen. Die zweiten gelten den seltenen Ausfällen: Man lässt Kanten häufiger ausfallen und rechnet das heraus. Die dritten gehen über das Schätzen hinaus: Welche Eingabe treibt die Streuung, wann darf man aufhören, was tun, wenn die Daten schon vorliegen, und welcher Schätzer gewinnt wann? Die Erklärseite zum Schätzer erzählt das Auswürfeln am Netz, die zu den seltenen Ausfällen, warum man sie gezielt häufiger ziehen muss, und die zum Aufhören, was ständiges Nachsehen mit dem Fehlerbereich macht.
Was diese Linie ist und was nicht: Alles ist an Gitternetzen und anderen gewählten Aufgaben mit exakt bekannter Lösung gerechnet (bei kleinen Gittern lässt sich die richtige Antwort exakt aufzählen), nichts stammt aus echten Daten. Nicht bestätigt hat sich, dass das Spiegeln der Zufallszahlen stets hilft: Bei seltenen Ausfällen bringt es kaum etwas, bei bestimmten symmetrischen Aufgaben verdoppelt es sogar die Varianz. Ebenso wenig stimmt die übliche Fehlerangabe bei seltenen Ereignissen, und ein kleiner Probelauf ersetzt die Regel nicht.
In short: Covers Monte Carlo estimation and its error bars: coupled draws, control variates, stratification, importance sampling, quasi-Monte Carlo, gradients, multilevel and nested estimators, stopping rules and the bootstrap. The last demo compares estimators.
Hintergrund zum Thema: Bestandsmanagement · Netzwerkdesign.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Monte-Carlo-Schätzer verständlich erklärt
Warum ein oft durchgespieltes Hochwasser die Ausfallchance eines Brückennetzes schätzt, wie langsam der Fehler sinkt und weshalb bei seltenen Ausfällen die Fehlerangabe trügt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Seltene Ausfälle schätzen verständlich erklärt
Warum „seit tausend Durchgängen kein Ausfall“ nicht „unmöglich“ heißt, wie man Ausfälle absichtlich häufiger macht und die Übertreibung danach wieder herausrechnet, und warum eine viel zu starke Übertreibung schlechter ist als keine: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Aufhören, sobald es gut aussieht, verständlich erklärt
Warum das übliche Vertrauensintervall nur für einen vorher festgelegten Umfang gilt, was ständiges Nachsehen anrichtet und was jederzeit gültige Intervalle kosten: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Der Bootstrap verständlich erklärt
Wie man aus zehn notierten Fahrzeiten ohne Formel die Unsicherheit ihres Durchschnitts erhält, indem man sie immer wieder neu mischt, und an welchen fünf Stellen die Fehlerangabe trügt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Das Rückgrat: vom Schätzer zur Verfahrenswahl
Die Wurzel ist der Monte-Carlo-Schätzer mit seiner Fehlerangabe: Der Fehler fällt mit der Wurzel der Zahl der Ziehungen, und die Varianz ist die Stellschraube. Daraus folgen die gekoppelten Ziehungen, die bei gleichem Aufwand die Varianz senken, dann die Kontrollvariaten, die einen bekannten Erwartungswert ausnutzen, und mehrere Modelle für den Fall, dass er unbekannt ist. Latin Hypercube deckt die Eingaben gleichmäßig ab, das bedingte Monte Carlo rechnet einen Teil exakt, Importance Sampling kippt die Ziehungen zu seltenen Ereignissen, und die Kreuzentropie lernt die Kippung.
Vom Latin Hypercube führt der Weg zum randomisierten Quasi-Monte-Carlo, das auch Wechselwirkungen gleichmäßig abdeckt; daran schließen die Sobol-Indizes und die Gradienten an, dann Multilevel für Diskretisierungsfehler und die geschachtelten Erwartungen, die auch das bedingte Monte Carlo aufgreifen. Abbruchregeln und Bootstrap beantworten, wann man aufhören darf und was man tut, wenn die Daten schon vorliegen. Die Verfahrenswahl führt Kreuzentropie, Quasi-Monte-Carlo und Bootstrap zusammen und verweist, wo Ziehen nicht geht, auf das Posterior-Sampling.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos anderer Linien: die Auswertung von Simulationsläufen aus den Warteschlangen und das Posterior-Sampling der Inversen Probleme. Doppelt umrandet ist die Verfahrenswahl, in der mehrere Stränge zusammenlaufen.
Verwandt in anderen Linien
- Warteschlangentheorie und Simulation — Die Auswertung von Simulationsläufen der Warteschlangen-Linie muss Warm-up und Autokorrelation beachten; hier sind die Ziehungen unabhängig, und es geht darum, bei gleichem Aufwand die Varianz zu senken, etwa mit gemeinsamen Zufallszahlen.
- Optimierung unter Unsicherheit — Die SAA-Demo ersetzt den Erwartungswert durch einen Stichprobenmittelwert; wie genau er ist und wie man ihn bei gleichem Aufwand genauer macht, zeigt diese Linie, zum Beispiel mit Latin Hypercube.
- Experimente und Wirkungsmessung — CUPED ist hier ein Spezialfall der Kontrollvariate; und die sequentiellen Tests der Experimente-Linie fragen wie die Abbruchregeln hier, was Zwischenblicke mit dem Intervall machen.
- Inverse Probleme und Regularisierung — Lässt sich die Verteilung nicht direkt ziehen, helfen unabhängige Ziehungen nicht mehr: Das Posterior-Sampling der Inversen Probleme nimmt Ketten, und die Verfahrenswahl hier nennt diese Frage als erste.
- Zustandsschätzung und Filter — Der Partikelfilter gewichtet Ziehungen und achtet darauf, wann die Gewichte entarten; dieselbe Diagnose, die effektive Stichprobengröße, nutzt das Importance Sampling hier für seltene Ausfälle.
- Abzählen und erzeugende Funktionen — Der Knuth-Schätzer schätzt die Zahl der Möglichkeiten aus zufälligen Pfaden, und Gleichverteilt ziehen liefert unabhängige Ziehungen aus einer Menge, die man nur zählen kann; Fehler und Zahl der Ziehungen folgen den Regeln dieser Linie.
- Reinforcement Learning — Der Score-Schätzer der Policy-Gradient-Demo ist einer von drei Wegen, eine Ableitung aus Ziehungen zu schätzen; die Gradienten-Demo misst ihn gegen den pfadweisen und den maßwertigen Schätzer.
- Bayessche Optimierung und Gauß-Prozesse — Die Versuchspläne der Surrogat-Demo und der Bayes-Opt-Demo verwenden Sobol-Punkte; was eine Sobol-Folge beim Schätzen leistet und wann sie wenig bringt, misst die Quasi-Monte-Carlo-Demo.
Der Monte-Carlo-Schätzer und sein Fehler
Sehen Sie, wie sich die Ausfallwahrscheinlichkeit eines Netzes durch Auswürfeln schätzen lässt: Man zieht zufällige Ausfallmuster und zählt, wie oft das Netz zerfällt. Die Demo kennt bei kleinen Gittern die richtige Antwort und misst daran Fehler und Vertrauensbereiche. Der Haken: Bei einem sehr stabilen Gitter sieht eine Stichprobe von 1000 Ziehungen mit Wahrscheinlichkeit 0,659 gar keinen Ausfall, und das übliche Intervall schrumpft auf einen Punkt, der die Wahrheit verfehlt.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Gekoppelte Ziehungen: Spiegelpaare und gemeinsame Zufallszahlen
Verfolgen Sie, wie sich Zufallsfehler gegeneinander ausspielen lassen: Man ersetzt jede Zufallszahl durch ihr Spiegelbild, oder man benutzt beim Vergleich zweier Netzentwürfe dieselben Zahlen. Die Demo misst, wie viel ruhiger die Schätzung wird; bei einem Gitter mit mittlerer Haltewahrscheinlichkeit sinkt das Schwankungsmaß (die Varianz) um 18 %. Der Haken: Bei seltenen Ausfällen bringt die Spiegelung kaum etwas, und bei bestimmten symmetrischen Funktionen verdoppelt sie die Varianz sogar.
Demo starten →Kontrollvariaten: bekannten Erwartungswert nutzen
Sehen Sie, wie sich eine Schätzung beruhigen lässt, indem man eine Hilfsgröße mit bekanntem Mittelwert mitzieht und ihre zufällige Abweichung davon abzieht. Ein Vergleich zeigt live, welche Hilfsgröße taugt: Bei seltenen Ausfällen senkt die Zahl isolierter Knoten die Varianz an einem Beispielgitter auf ein Siebenunddreißigstel, die naheliegende Zahl haltender Kanten bringt praktisch nichts. Der Haken: Das übliche Intervall unterdeckt dort, selbst mit dem besten Korrekturgewicht.
Demo starten →Mehrere Modelle: das billige Modell darf falsch sein
Beobachten Sie, wie eine billige, grobe Näherung eine teure Rechnung entlastet: Die Näherung läuft auf vielen Eingaben, die teure Rechnung auf wenigen, und die Differenz auf den gemeinsamen Eingaben korrigiert den Fehler, auch wenn die Näherung verzerrt ist. Im Standardfall sinkt die Varianz auf rund 16 %. Der Haken: Die naheliegende billige Wahl, der Zusammenhangstest, ist schlechter als gar keine, und mit einem schnelleren teuren Verfahren schrumpft der Gewinn.
Demo starten →Schichtung und Latin Hypercube: gleichmäßig abdecken
Sehen Sie, wie Latin Hypercube die Zufallspunkte gleichmäßig verteilt: Der Wertebereich jeder Eingabe wird in gleiche Schichten geteilt, aus jeder kommt ein Punkt, sodass weniger Lücken und Klumpen entstehen. Die Demo sagt den Gewinn vorher, den Faktor 0,264 für zwei Dreiecke mit einer Brücke bei hoher Haltewahrscheinlichkeit, und prüft ihn nach. Der Haken: Bei seltenen Ausfällen zeigt sich der Gewinn erst, wenn eine Stichprobe etwa einen Ausfall enthält.
Demo starten →Bedingtes Monte Carlo: einen Teil exakt ausrechnen
Sehen Sie, wie man einen Teil der Zufallsunsicherheit nicht auswürfelt, sondern ausrechnet: Für ausgewählte Kanten werden alle Zustände durchgerechnet, nur der Rest wird gezogen. Die Demo vergleicht bei gleichem Rechenbudget; beim Netz mit einer Brücke sinkt die Varianz so auf den Faktor 0,646. Der Haken: Im Gitter lohnt das bei nicht allzu seltenen Ausfällen oft gar nicht, denn das Durchrechnen kostet Aufwand, und die Wahl der Kanten entscheidet.
Demo starten →Importance Sampling: seltene Ausfälle schätzen
Verfolgen Sie, wie sich seltene Ausfälle schätzen lassen, indem man Kanten häufiger ausfallen lässt und jede Ziehung umgewichtet. Ein Regler für diese Kippung zeigt live den Effekt: Für zehn Prozent Fehler braucht einfaches Ziehen im Beispiel 239 737 Ziehungen, mit guter Kippung 8057. Der Haken: Zu starkes Kippen ist schlechter als gar nicht zu kippen, und die gängige Warnzahl gibt in diesem Netz selbst bei bester Wahl Fehlalarm.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Kreuzentropie: die Hilfsverteilung lernen
Beobachten Sie, wie die Kippung für Importance Sampling stufenweise aus den Ziehungen gelernt wird: Man behält die besten Ziehungen, die Elite, richtet die Kippung an ihnen aus und wiederholt. Im Standardfall genügen zwei Stufen, und die relative Varianz liegt nur beim 1,01-fachen des Optimums. Der Haken: Wählt man die Elite zu groß, bleibt das Lernen in einem Zwischenstand stecken und erreicht den Ausfall nicht.
Demo starten →Randomisiertes Quasi-Monte-Carlo: wann gewinnt die Sobol-Folge?
Sehen Sie, wie eine Punktfolge, die den Raum aller Eingaben gleichmäßig füllt (Sobol-Folge), mit einem Zufallsanteil gemischt wird, damit der Schätzer unverzerrt bleibt. Frühere Verfahren sicherten die Gleichmäßigkeit nur je einzelner Eingabe. Ein Vergleich zeigt live, wie der Gewinn von Eingabezahl und Glattheit der Aufgabe abhängt. Der Haken: Bei einer Beispielaufgabe mit acht Eingaben und 1024 Punkten ist der übliche Fehlerbalken 34-mal so breit wie der wahre Fehler.
Demo starten →Sobol-Indizes: welche Eingabe treibt die Varianz?
Verfolgen Sie, wie man aus Modellläufen schätzt, welcher Anteil der Schwankung des Ergebnisses an welcher Eingabe hängt: Für jede Eingabe wird nur deren Zufallswert ausgetauscht. Die Demo zeigt, wie genau das wird und wie viele Läufe es kostet. Der Haken: Ein kleiner Einzelanteil geht im Rauschen unter. Beim kleinsten Anteil eines Gitternetzes (0,0024) ist der Fehler selbst bei 10 000 Ziehungen ein Mehrfaches davon.
Demo starten →Gradienten schätzen: pfadweise, Score oder maßwertig?
Beobachten Sie, wie man aus gezogenen Szenarien schätzt, wie stark sich ein erwarteter Wert ändert, wenn man einen Parameter der Nachfrage verschiebt. Drei Wege konkurrieren: durch die Rechnung hindurch ableiten (pfadweise), die Wahrscheinlichkeit ableiten (Score) oder die Verteilung zerlegen (maßwertig). Die Demo zeigt, welcher je nach Glattheit am genauesten ist. Der Haken: Bei einer Ja-Nein-Größe liefert der pfadweise Weg null, eine Verzerrung von −100 %.
Demo starten →Multilevel Monte Carlo: wann sich die Ebenen lohnen
Sehen Sie, wie sich ein Erwartungswert, den nur ein Zeitschrittverfahren liefert, billiger schätzen lässt: Viele Bahnen rechnet man grob, nur die Korrektur zur feinen Rechnung braucht wenige teure Bahnen, solange beide dieselben Zufallszuwächse nutzen. Der Haken: Bei lockerer Toleranz gewinnt gewöhnliches Monte Carlo, bei einer Ja-Nein-Größe verliert im gezeigten Bereich das einfachere Zeitschrittverfahren, und nur mit dem genaueren ist es bei Toleranz 0,000625 beim Fehlbestand 57-mal billiger.
Demo starten →Geschachtelte Erwartungen: Erwartungswert über Erwartungswert
Sehen Sie, wie man eine Größe schätzt, in der ein Erwartungswert in einem Erwartungswert steckt: Naiv zieht man außen viele Werte und je Wert innen nochmals viele, und die Kosten steigen mit der dritten Potenz der geforderten Genauigkeit. Die Demo zeigt, wann gestufte Rechnung das rettet. Der Haken: Sie braucht eine geschickte Kopplung, kostet bei einer Ja-Nein-Größe im gemessenen Bereich mehr, und bei lockerer Toleranz gewinnt das einfache Schachteln.
Demo starten →Abbruchregeln: wann man aufhören darf
Beobachten Sie, was geschieht, wenn man eine Simulation laufen lässt, bis das Ergebnis gut genug aussieht. Übliche Vertrauensintervalle gelten nur für einen vorher festgelegten Umfang; wer ständig nachsieht, liegt bei einem Beispielnetz in einem Anteil von 0,62 der Läufe irgendwann außerhalb. Die Demo zeigt Intervalle, die auch beim jederzeitigen Anhalten halten. Ihr Preis: bei diesem Netz und einer relativen Genauigkeit von 0,2 das 4,04-Fache an Proben.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Bootstrap: wann Resampling die Verteilung ersetzt
Sehen Sie, wie man aus vorhandenen Daten, etwa einem Log, die Unsicherheit einer beliebigen Kennzahl ohne Formel erhält: Man zieht aus den Daten mit Zurücklegen neue Datensätze und liest die Streuung ab. Die Demo prüft, wie oft das 95-%-Intervall die bekannte Wahrheit trifft. Der Haken: Bei zehn schiefen Dauern deckt das einfache Intervall den Mittelwert nur in 0,826 der Fälle, und bei 500 Werten mit starker Abhängigkeit nur in 0,510.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Verfahrenswahl: welcher Schätzer wann?
Sehen Sie, wie sich bei elf Aufgaben mit bekannter Lösung zeigt, welcher Schätzer bei gleich vielen Auswertungen am genauesten ist und ob seine Fehlerangabe stimmt. Meist gewinnt die gleichmäßig gemischte Sobol-Punktfolge, bei seltenen Netzausfällen die gezielte Gewichtung (Importance Sampling); gekippt wird in diesen Netzen bei einigen Dutzend erwarteten Treffern. Der Haken: Ein kleiner Probelauf ersetzt die Regel nicht und ist bei seltenen Ereignissen blind.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über die Stücke: Er fragt nach der Aufgabe, nicht nach dem Verfahren. Liegen die Daten schon vor, muss man anhalten dürfen, will man eine Ableitung, hat die Aufgabe Struktur, ist das Ereignis selten, ist sie glatt?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Wo mehrere Stücke passen, hilft die Verfahrenswahl; ihre Schwelle für seltene Ereignisse ist an Gitternetzen gemessen und nicht scharf.
Weitere Linien in diesem Bereich
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Dynamische Systeme
Eine Regel, die man immer wieder auf ihr eigenes Ergebnis anwendet: elf Stücke vom Ruhepunkt über Kreislauf und Chaos bis zu Verzögerung, Kopplung und Lernen.
Rückkopplung und Verzögerung
Ein Lager bestellt nach einer einfachen Regel nach, während die Ware Zeit braucht: fünf Stücke von der Lieferzeit über die Ware unterwegs und die späte Meldung bis zur streuenden Lieferzeit und zur Saison.