Wie gewichtete Zufallsauswahl funktioniert

Die gewichtete Zufallsauswahl wird verwendet, wenn Optionen nicht die gleiche Wahrscheinlichkeit haben sollen. Gewichte geben an, wie oft jede Option im Durchschnitt gewinnen sollte.

Wichtige Erkenntnisse

• Wahrscheinlichkeit = Gewicht geteilt durch das Gesamtgewicht.
• Kumulative Gewichtungen verwandeln Optionen in Segmente des Intervalls von 0 bis 1.
• Ein sicherer Zufallswert wählt einen Punkt aus; das passende Segment gewinnt.
• „Gewichtet ohne Ersatz“ entfernt den Gewinner und normalisiert die verbleibenden Gewichte neu.
• Testen Sie die Fairness, indem Sie beobachtete und erwartete Häufigkeiten über viele Ziehungen hinweg vergleichen.

Gleiche versus gewichtete Zufälligkeit

Ein gewöhnlicher Zufallswähler behandelt jede Option gleich. Das ist richtig für eine Auslosung im Klassenzimmer, bei der jeder Schüler die gleiche Chance haben sollte. Aber viele echte Entscheidungen sind bewusst ungleich:

• Ein Spiel möchte, dass gewöhnliche Beute häufig und seltene Beute selten erscheint.
• Bei einer Tombola erhalten einige Teilnehmer mehr Tickets als andere.
• Ein A/B-Test führt 80 % der Nutzer zur Kontrollvariante und 20 % zur neuen Variante.
• Ein Lehrer möchte, dass schwierige Fragen häufiger gestellt werden als einfache.

Gewichtete Zufälligkeit ist immer noch Zufälligkeit. Der Unterschied besteht darin, dass die Wahrscheinlichkeitsverteilung beabsichtigt ist.

Gewichte sind Wahrscheinlichkeiten, keine Zählwerte

Das Gewicht einer Option ist selbst keine Wahrscheinlichkeit. Es handelt sich um eine relative Zahl. Um eine Wahrscheinlichkeit zu erhalten, dividieren Sie das Gewicht durch die Summe aller Gewichte.

Angenommen, die Optionen sind:

• A, Gewicht 1.
• B, Gewicht 2.
• C, Gewicht 7.

Das Gesamtgewicht beträgt 10, die Wahrscheinlichkeiten betragen also 10 %, 20 % und 70 %. Wenn Sie 100 Mal ziehen, sollte C etwa 70 Mal gewinnen. Wenn Sie nur 10 Mal ziehen, könnte C 4, 6 oder sogar 0 Mal gewinnen. Kleine Samples sind laut; Die Gewichte beschreiben die langfristige Erwartung.

Die kumulative Verteilung

Die kumulative Verteilung wandelt diese Gewichte in Segmente des Intervalls von 0 bis 1 um. Mit dem gleichen Beispiel:

• A deckt 0,00 bis 0,10 ab.
• B deckt 0,10 bis 0,30 ab.
• C deckt 0,30 bis 1,00 ab.

Die Breite jedes Segments ist die Wahrscheinlichkeit der Option. Die Segmente überlappen sich nicht und decken zusammen das gesamte Intervall ab.

Aus diesem Grund benötigt die gewichtete Auswahl nicht für jede Option eine eigene Wahrscheinlichkeit. Sie benötigen lediglich die Gewichte und deren Summe.

Inverse Transformationsabtastung

Die inverse Transformationsstichprobe ist die Standardmethode zur Auswahl aus dieser Verteilung:

1. Berechnen Sie das Gesamtgewicht.
2. Wählen Sie einen Zufallswert zwischen 0 und der Gesamtsumme.
3. Gehen Sie die Optionen durch und addieren Sie jedes Gewicht zu einer laufenden Gesamtsumme.
4. Stoppen Sie bei der ersten Option, deren kumulatives Gewicht größer oder gleich dem Zufallswert ist.

Die ausgewählte Option ist der Gewinner. Wenn der Zufallswert im Segment von A landet, gewinnt A. Wenn es im Segment von C landet, gewinnt C.

Der Algorithmus benötigt O(n) Zeit pro Ziehung, wobei n die Anzahl der Optionen ist. Es ist einfach, korrekt und mehr als schnell genug für eine Seite mit ein paar Dutzend Optionen.

Mit und ohne Ersatz

Beim Austausch ist jede Ziehung unabhängig. Die gleiche Option kann mehr als einmal gewinnen. Dies ist das richtige Modell, wenn bei jeder Ziehung die ursprünglichen Wahrscheinlichkeiten verwendet werden sollten.

Eine ausgewählte Option wird ersatzlos aus dem Pool entfernt. Die verbleibenden Gewichte werden vor der nächsten Ziehung renormiert. Wenn A entfernt wird, ist die verbleibende Summe kleiner, sodass B und C größere Anteile an der nächsten Ziehung erhalten.

Ohne Ersatz geht es nicht. Es erzeugt nicht jede Permutation mit gleicher Wahrscheinlichkeit. Es entsteht eine gewichtete Reihenfolge: Optionen mit größeren Gewichtungen erscheinen tendenziell früher.

Die Alias-Methode für großvolumige Picks

Für eine große Anzahl von Draws oder sehr große Optionssätze gibt es eine schnellere Alternative namens Alias-Methode. Es erstellt einmal eine Nachschlagetabelle und beantwortet dann jede Ziehung in konstanter Zeit.

Die Alias-Methode ist in Spielen und Simulationen nützlich, die Millionen von Picks erfordern. Für ein Browser-Tool mit einer kleinen Liste ist die kumulative inverse Transformationsstichprobe einfacher und vollkommen ausreichend.

Häufige Fehler

Gewichte können leicht falsch sein. Achten Sie auf diese Fehler:

• Eine Gewichtung von 70 wird als 70 % behandelt, wenn die anderen Gewichte nicht Null sind. Sie beträgt nur 70 %, wenn die Summe der anderen Gewichte 30 oder weniger beträgt.
• Zulassen von Null- oder Negativgewichten. Optionen mit Nullgewicht können niemals gewinnen. Negative Gewichte machen die Verteilung bedeutungslos.

– Verwendung von Math.random() für eine Auslosung, die unvorhersehbar sein muss. – Verwenden einer voreingenommenen Zuordnung, um Zufallswerte in Segmente umzuwandeln.

• Beurteilung der Fairness anhand von zehn oder zwanzig Ziehungen. Kleine Stichproben können stark von der erwarteten Verteilung abweichen.

Ein weiterer häufiger Fehler besteht darin, Gewichtung mit Mischen zu verwechseln. Wenn Sie jede Permutation mit gleicher Wahrscheinlichkeit benötigen, mischen Sie die Liste. Wenn Sie einen gewichteten ersten Pick benötigen, verwenden Sie einen gewichteten Zug.

So überprüfen Sie einen gewichteten Zug

Vergleichen Sie erwartete und beobachtete Häufigkeiten. Bei den Gewichtungen 1, 2 und 7 betragen die erwarteten Wahrscheinlichkeiten 10 %, 20 % und 70 %. Bei Tausenden von Ziehungen sollten sich die beobachteten Anteile diesen Zahlen annähern.

Überinterpretieren Sie eine kleine Stichprobe nicht. Ein fair gewichteter Draw kann zu einer Überraschungssträhne führen. Entscheidend ist, ob die beobachteten Häufigkeiten mit zunehmender Stichprobe konvergieren und ob die Umsetzung dokumentiert ist.

Notieren Sie bei einer öffentlichen gewichteten Auslosung die Optionen, Gewichte und das Ergebnis. Dadurch ist die Auslosung auch dann überprüfbar, wenn Sie den Code nie veröffentlichen.

Wie diese Site gewichteten Zufall implementiert

Der gewichtete Picker auf dieser Website verwendet kumulative Gewichte und einen kryptografisch sicheren Zufallswert. Die Wahrscheinlichkeitsvorschau zeigt die normalisierte Verteilung, bevor Sie zeichnen. Optionen werden mit inverser Transformationsabtastung ausgewählt, und Ziehungen ohne Ersatz entfernen die ausgewählte Option und normalisieren die verbleibenden Gewichte neu.

Alles läuft lokal in Ihrem Browser. Ihre Optionen, Gewichte und Ergebnisse werden nicht hochgeladen.

Fazit

Gewichtete Zufälligkeit verändert die Wahrscheinlichkeiten, nicht die Quelle der Zufälligkeit. Normalisieren Sie die Gewichte, verwenden Sie einen sicheren Zufallswert und wählen Sie das passende kumulative Segment aus. Dadurch erhalten Sie faire ungleiche Wahrscheinlichkeiten für Beutetische, Tombola, A/B-Tests und Unterrichtsaktivitäten.